版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "题解 - [Luogu P1244] [NOI2000] 青蛙过河" categories:
有一条河, 左边一个石墩(A 区)上有编号为 $1, 2, 3, 4, …, n$ 的 $n$ 只青蛙, 河中有 $k$ 个荷叶(C 区), 还有 $h$ 个石墩(D 区), 右边有一个石墩(B 区), 如下图所示.
$n$ 只青蛙要过河(从左岸石墩 A 到右岸石墩 B), 规则为:
(1)石墩上可以承受任意多只青蛙, 荷叶只能承受一只青蛙(不论大小);
(2)青蛙可以: $A\to B$(表示可以从 A 跳到 B, 下同), $A\to C, A\to D, C\to B, D\to B, D\to C, C\to D$;
(3)当一个石墩上有多只青蛙时, 则上面的青蛙只能跳到比它大 1 号的青蛙上面.
你的任务是对于给出的 $h, k$, 计算并输出最多能有多少只青蛙可以根据以上规则顺利过河?
两个整数 $h,k\ (h<20 , k<1000)$
一个整数, 表示最多能有多少只青蛙可以根据以上规则顺利过河.
2 3
16
打表可得 答案为 $2^h(k+1)$
令 $f(h,k)$ 为 $h$ 个石墩, $k$ 个荷叶的结果
显然有
$$ f(h,k)=\begin{cases} k+1,&h=0\ 2f(h-1,k),&h>0 \end{cases} $$
故 $f(h,k)=2^h(k+1)$
代码略