洛谷P1244青蛙过河题解_C

我用的是C++来解

其实这道题很简单，只要弄清楚关系就行，和汉诺塔问题相似。不用细想顺序（青蛙就是乱跳），可将青蛙作为一个整体来想。

我们用f[h][k]表示h个石墩和k片荷叶最多的青蛙数

f[0][k] = k+1

h=1时，让更多的青蛙站到D,B石墩上，然后D--->B，得到f[1][k] = f[0][k] + f[0][k]

h=2时也一样，让D区第一个石墩站满青蛙后跳到第二个石墩，再把B区塞满，再让D区第二个石墩上的青蛙跳到B上，最后D1--->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]

由于空石墩的数量是一样的，所以青蛙一定会跳到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)

上代码：

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

 
位运算是出于省事（tou lan zhuang bi）的考虑 
喜欢请点赞，不足处请神犇们留下你的评论吧~ 
我的个人博客：GARS 的博客
欢迎分享，转载请注明来源：内存溢出
原文地址:https://54852.com/langs/676414.html

洛谷P1244青蛙过河题解