洛谷 P1244 [NOI2000] 青蛙过河 题解 2023-02-23 OI 暂无评论 586 次阅读 # [NOI2000] 青蛙过河 https://www.luogu.com.cn/problem/solution/P1244 ## 题解 所以假设没有石礅时，有 $$k$$ 片荷叶，每片荷叶可以站一只青蛙，右面石礅可以站一只青蛙，共 $$k+1$$ 只青蛙，我们记为转移了编号为 $$1,2,3,\cdots, s$$ 的 $$s$$ 只青蛙 现在增加石礅，假设增加了一个石礅 $$D$$，则可以让编号为 $$1,2,3,\cdots, s$$ 的 $$s$$ 只青蛙站在 $$D$$ 上，让编号为 $$s+1,s+2,s+3,\cdots, 2s$$ 的 $$s$$ 只青蛙站在 $$B$$ 上，最后让 $$D$$ 上的青蛙转移到 $$B$$，总共有 $$2s$$ 只青蛙，每增加一个石礅，都可以让转移的青蛙数乘 $$2$$，从而得到递推关系式。 ## 题目描述 **大小各不相同**的一队青蛙站在河左岸的石墩（记为 A ）上，要过到对岸的石墩(记为 D )上去。河心有几片菏叶（分别记为 $$Y_1 \dots Y_m$$）和几个石墩（分别记为 $$S_1\dots S_n$$）。图示如下  青蛙的站队和移动方法规则如下： - 每只青蛙只能站在荷叶、石墩，或者**仅比它大一号**的青蛙背上（统称为合法的落脚点）； - 一只青蛙只有背上没有其它青蛙的时候才能够从一个落脚点跳到另一个落脚点； - 青蛙允许从左岸 A 直接跳到河心的石墩、荷叶和右岸的石墩 D 上，允许从河心的石墩和荷叶跳到右岸的石墩 D 上； - 青蛙在河心的石墩之间、荷叶之间以及石墩和荷叶之间可以来回跳动； - 青蛙在离开左岸石墩后，不能再返回左岸；到达右岸后，不能再跳回； - 假定石墩承重能力很大，允许无论多少只青蛙都可呆在上面。但是，由于石墩的面积不大，至多只能有一只青蛙直接站在上面，而其他的青蛙只能依规则 1 落在比它大一号的青蛙的背上。 - 荷叶不仅面积不大，而且负重能力也有限，至多只能有一只青蛙站在上面。 - 每一步只能移动一只青蛙，并且移动后需要满足站队规则； - 在一开始的时候，青蛙均站在 A 上，最大的一只青蛙直接站在石墩上，而其它的青蛙依规则 6 站在比其大一号的青蛙的背上。 青蛙希望最终能够全部移动到 D 上，并完成站队。 设河心有 $$m$$ 片荷叶和 $$n$$ 个石墩，请求出这队青蛙至多有多少只，在满足站队和移动规则的前提下，能从 A 过到 D。 你的任务是对于给出的 $$n,m$$，计算并输出最多能有多少只青蛙可以根据以上规则顺利过河。 ## 输入格式 输入两个整数 $$n,m$$。 ## 输出格式 一个整数，表示最多能有多少只青蛙可以根据以上规则顺利过河。 ## 样例 #1 ### 样例输入 #1 ``` 1 1 ``` ### 样例输出 #1 ``` 4 ``` ## 提示 $$n \leq 20$$，$$m \leq 10^3$$。 标签: 洛谷, 题解, 算法 本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。