题目传送门

解题思路：

接下来便是核心内容：(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;

//原址：https://www.luogu.com.cn/blog/wucstdio/solution-p1244

AC代码：

 1 #include<iostream>
 2 #include<cstdio>
 3 
 4 using namespace std;
 5 
 6 int h,k,f[100001],t;
 7 
 8 int main() {
 9     scanf("%d%d",&h,&k);
10     f[1] = k + 1;
11     t += f[1];
12     for(int i = 1;i <= h; i++) {
13         f[i] = t + k + 1;
14         t += f[i];
15     }
16     printf("%d",f[h]);
17     return 0;
18 } 

洛谷 P1244 青蛙过河

原文：https://www.cnblogs.com/lipeiyi520/p/12037479.html