P1244 青蛙过河
题目描述
有一条河，左边一个石墩(A区)上有编号为1，2，3，4，…，n的n只青蛙，河中有k个荷叶(C区)，还有h个石墩(D区)，右边有一个石墩(B区)，如下图所示。n只青蛙要过河(从左岸石墩A到右岸石墩B)，规则为：
(1)石墩上可以承受任意多只青蛙，荷叶只能承受一只青蛙(不论大小)；
(2)青蛙可以：A→B(表示可以从A跳到B，下同)，A→C，A→D，C→B，D→B，D→C，C→D；
(3)当一个石墩上有多只青蛙时，则上面的青蛙只能跳到比它大1号的青蛙上面。
你的任务是对于给出的h，k，计算并输出最多能有多少只青蛙可以根据以上规则顺利过河?
输入输出格式
输入格式：
两个整数h,k
输出格式：
一个整数，表示最多能有多少只青蛙可以根据以上规则顺利过河。
输入输出样例
2 3
16
分析：
情况一：
当k确定而h=0时,没有中间柱子,蛤蛤们只能通过荷叶来移动.每片荷叶只能有1位青蛙.所以要求最大的通过数目就必须把所有的荷叶用上.
由于他们必须按顺序从小到大从上到下垒起来（跳到石墩B上面的时候）.所以这种情况下,最大通过数目为k+1.
就是石墩B上面跳一只，其余每片荷叶上面跳一只。
因为题目要求中青蛙可以直接到B。
(2)青蛙可以：A→B(表示可以从A跳到B，下同)，A→C，A→D，C→B，D→B，D→C，C→D；
情况二：
当k确定而h=1时,有一个中间柱子s1。
先将1->k+1号（1k+1个）放在s1石墩上，然后将k+2->2k+2号（1k+1个）放到全部荷叶和石墩B上。
情况三：
当k确定而h=2时,有两个中间柱子s1，s2。
先将1->2k+2号（2k+2个）放在s1石墩上，然后将2k+3->3k+3号（1k+1个）放在s2石墩上，
然后再将3k+4->4k+4（1k+1个）放到全部荷叶和石墩B上。
既然如此我们用 f[h][k] 表示 h 个石墩 k 片荷叶时最多的青蛙数
显然 f[0][k]=k+1
h=1时，让尽可能多的青蛙跳到D区石墩上（f[0][k]），再让尽可能多的青蛙跳到B石墩上（f[0][k]），最后让D区石墩上的青蛙跳到B上，所以 f[1][k]= f[0][k] + f[0][k]。
h=2时，让尽可能多的青蛙跳到D区的第一个石墩上（f[1][k]），再让尽可能多的青蛙跳到D区的第二个石墩上（f[0][k]），再让尽可能多的青蛙跳到B石墩上（f[0][k]），再让D区第二个石墩上的青蛙跳到B石墩上，最后让D区第一个石墩上的青蛙跳到B上，所以 f[2][k]=f[1][k]+ f[0][k] + f[0][k]。
以此类推。f[h][k]=f[h-1][k]+f[h-2][k]+…+f[1][k]+f[0][k]+f[0][k]
由于青蛙跳到D区石墩上和从D区跳到B上环境是一样的（即空石墩的数量是一样的），所以不用担心青蛙跳不到B上啦。
得到递推公式之后，让我们再来看一看。
f[1][k]= f[0][k] + f[0][k]=2*(k+1)
f[2][k]=f[1][k]+ f[0][k] + f[0][k] =f[1][k]+f[1][k]=2*2*(k+1)
f[3][k]=f[2][k]+ f[1][k]+ f[0][k] + f[0][k]=f[2][k]+f[2][k]=2*2*2*(k+1)
… f[h][k]=2*f[h-1][k]=(2^h)*(k+1)
于是我们得到了通项公式f[h][k] =(2^h)*(k+1)
1 #include<iostream> 2 #include<math.h> 3 using namespace std; 4 int main() 5 { 6 int i,j,m,h,k,a; 7 while(cin>>h>>k) 8 cout<<(k+1)*pow(2,h)<<endl; 9 }