题解 P1244 【青蛙过河】

· · 题解

这道题还是比较坑爹的……

首先，青蛙只能往前跳，不能往后跳，而且只能12345这样排下去，所以要想使最多的青蛙到达对岸，只需使编号最大的青蛙首先跳到对岸（否则编号更大的青蛙就跳不过去了）。

然后，要想使编号最大的青蛙首先跳到对岸，只需让河面上承载最多的青蛙。而荷叶上只能承载一只青蛙，所以需要让青蛙尽可能多地叠到石墩上。

接下来便是核心内容：(f[i]表示当有k个荷叶，i个石墩时过河青蛙的最大数量)

1、若有k个荷叶，没有石墩，则最多有k+1个青蛙。所以f[0]=k+1（不需要解释了吧）；

2、若有k个荷叶，1个石墩，则只需要使石墩上承载最多的青蛙。进一步分析，我们只需要将石墩当做对岸，这样就变成1的情况了。所以f[1]=f[0]+k+1；

3、若有k个荷叶，2个石墩，则需要先让石墩1作为对岸，叠完后再让石墩2作为对岸。所以f[2]=f[1]+f[0]+k+1；

继续往下推理，得到状态转移方程：f[h]=f[0]+f[1]+f[2]+……+f[h-1]+k+1;

下面是代码：

#include<cstdio>
using namespace std;
int h,k,f[20000];
int main()
{
    scanf("%d%d",&h,&k);
    f[0]=k+1;//初始化
        int t=f[0]+k+1;//设置变量t避免重复相加
        for(int i=1;i<=h;i++)
        {
                f[i]=t;
                t+=f[i];
        }
        printf("%d\n",f[h]);
        return 0;
}