NKOJ全TJ计划——NP1397

题目内容

有一条河，左边一个石墩(A区)上有编号为\(1\backsim n\)的只青蛙，河中有个\(k\)荷叶(C区)，还有个\(h\)石墩(D区)，右边有一个石墩(B区)，如下图所示。

\(n\)只青蛙要过河(从左岸石墩A到右岸石墩B)，规则为：

石墩上可以承受任意多只青蛙，荷叶只能承受一只青蛙(不论大小)；
青蛙可以：A→B(表示可以从A跳到B，下同)，A→C，A→D，C→B，D→B，D→C，C→D；
当一个石墩上有多只青蛙时，则上面的青蛙只能跳到比它大1号的青蛙上面。

你的任务是对于给出的\(h,k\)，计算并输出最多能有多少只青蛙可以根据以上规则顺利过河?
\(0\le h,k\le 20\)

解决方法

我们设\(f_{i,j}\)为\(i\)个石墩,\(j\)个荷叶时的最大方案。
则\(f_{0,j}=j+1\)。
当\(h=1\)时,我们可以先让最多的青蛙从\(A\)跳到\(S_1\)(\(f_{0,j}\)),再让最多的青蛙从\(A\)跳到\(D\)(\(f_{0,j}\)),再让青蛙们从\(S_1\)跳到\(D\)(无贡献)。
以此类推,可以得到\(f_{i,j}=f_{0,j}+\sum_{k=1}^{i-1} f_{k,j}=2^i\times f_{0,j}=2^i\times (j+1)\)

代码

#include<bits/stdc++.h>
using namespace std;
int a,b,c;
int main()
{cin>>a>>b;c=pow(2,a);cout<<(b+1)*c;
}