P1244 NOI2000青蛙过河 [思维题]

$青蛙过河$

题目见标题链接 .

---

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

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

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

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

再考虑 $F[2, 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[i, j] = 2^i * F[0,j] = 2^i*(j+1).$

---

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

#include<bits/stdc++.h>
#define reg register

int h;
int k;

int main(){
        scanf("%d%d", &h, &k);
        printf("%d
", (1<<h) * (k+1));
        return 0;
}