青蛙过河青蛙过河青蛙过河

题目见标题链接 .

---

正解部分\color{red}{正解部分}正解部分

开始前先说明 若跳到 BBB 点, 则不能跳出 .

设 F[i,j]F[i, j]F[i,j] 表示 iii 个石墩, jjj 个荷叶的最优答案,

首先 F[0,j]=j+1F[0, j] = j+1F[0,j]=j+1, 这很直观 , 然后考虑 F[1,j]F[1, j]F[1,j] 的值,
现在中间有一个石墩, 设为 DDD, 从起点先跳到 DDD, 然后从起点跳到终点, 再把 DDD 点的青蛙跳到 终点,
可以得到 F[1,j]=F[0,j]+F[0,j]=2∗F[0,j]F[1, j] = F[0, j] + F[0, j] = 2*F[0,j]F[1,j]=F[0,j]+F[0,j]=2∗F[0,j] .

再考虑 F[2,j]F[2, j]F[2,j] 的值, F[2,j]=F[1,j]+F[0,j]+F[0,j]=4∗F[0,j]F[2, j] = F[1, j] + F[0, j] + F[0, j] = 4*F[0, j]F[2,j]=F[1,j]+F[0,j]+F[0,j]=4∗F[0,j]
同理 F[3,j]=F[2,j]+F[1,j]+F[0,j]+F[0,j]=8∗F[0,j]F[3, j] = F[2, j] + F[1, j] + F[0, j] + F[0, j]=8*F[0,j]F[3,j]=F[2,j]+F[1,j]+F[0,j]+F[0,j]=8∗F[0,j],
以此类推可得 F[i,j]=2i∗F[0,j]=2i∗(j+1).F[i, j] = 2^i * F[0,j] = 2^i*(j+1).F[i,j]=2i∗F[0,j]=2i∗(j+1).

---

实现部分\color{red}{实现部分}实现部分

#include#define reg registerint h;int k;int main(){ scanf("%d%d", &h, &k); printf("%d\n", (1<