P1244 [NOI2000] 青蛙过河 分析

· · 个人记录

我觉得是一道比较好的思维题。

当只有 m 个荷叶的时候，明显我们最多有 m + 1 个青蛙。从 A 出发依次跳到 m 个荷叶上，最后一只青蛙直接跳到 D，然后再顺次跳到 D 上即可。

我们看石墩。石墩增加一个，可以过的青蛙翻倍。很简单，我们设原来有 m 个荷叶，那么最多能过 m + 1 个青蛙。增加石墩后，我们让前 m 个青蛙跳到荷叶上，第 m + 1 个跳到石墩上，然后让这 m 个再跳到那个石墩上，现在这个石墩上就有了 m + 1 只青蛙。之后我们按照原来的方法转移即可。

于是最终的答案就是：(m + 1) \times 2^n。