题解 - [Luogu P1244] [NOI2000] 青蛙过河

发表于 2020-01-15 更新于 2024-07-02 分类于算法竞赛，题解本文字数： 363 阅读时长 ≈ 1 分钟

原始题面

有一条河，左边一个石墩 (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

~~打表可得~~ 答案为 \(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)\)

代码略