题解 P1244 【青蛙过河】

· · 题解

必须承认一开始看了很久才看懂题目哇QAQ

原来A和B也是石墩，青蛙也要按大小排不能一个一个跳过去哇QAQ

既然如此我们用 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)

下面是代码：

#include <iostream>
using namespace std;
int main(){
    int h,k;
    cin>>h>>k;
    cout<<(k+1)*(1<<h);
    return 0;
}

位运算呢是出于省(zhuang)时(bi)的考虑。 还有就是题目中没有给出数据范围，原题中应该是 h<20 , k<1000 来着，所以不用 long long更不用高精度啦。