首页 > [NOI2000]青蛙过河
开通博客写题解
头像 HGDB
发表于 2020-05-12 20:41:32
题目 思路 题目大意就是n个石墩，m个荷叶，石墩可以站很多青蛙，荷叶只能站一个，青蛙过河后不能回去，青蛙必须按照汉诺塔站在石墩上，求最多的过河青蛙数。 先假设 n == 0，那就让每个青蛙都在一个荷叶上，初始石墩剩一个青蛙直接过河，能过m+1个青蛙 然后 n == 1 ，让每个青蛙都在 展开全文
去ta的博客 赞 (13) 回复(0) 收起
头像 TA很酷
发表于 2020-05-13 17:17:55
n片荷叶，k个石墩若k=0，那么在每片荷叶上放一只青蛙，最后从岸上直接跳到对面一只青蛙，可以有 n+1 只青蛙过岸若k=1，那么我们可以在这个石墩上叠n+1只青蛙，然后就又变为k=0的情况然后，每多一个石墩就可以利用原来的k−1个石墩把它们的青蛙全部放到这上面来，这样就增加了一倍的青蛙可以过岸 也就 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 998244353
发表于 2020-05-13 02:31:34
题意：类似汉诺塔问题，但是需要分析细节。题解： 荷叶数为，石墩数为。当，那么最多先个到荷叶，第个到终点。当，那么最多个到荷叶和石墩，然后荷叶上的个再到石墩。情况转换为的情况，两者相加即当，那么最多先个到荷叶和石墩1，然后荷叶上的到石墩1，之后再有个到荷叶和石墩2，然后这个到石墩1。情况转换为了的情况 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 sunrise__sunrise
发表于 2020-05-12 22:17:35
A、青蛙过河 是不是乍一眼看起来像哈诺塔……恭喜你被骗了。汉诺塔可以随意移动，虽然也有一定前提。但是对这个题目来说最要命的约束条件就是到了对面就不能动了。所以就决定了，一定是重的青蛙先跳去对面。所以我们从几个极端来看。如果给出莲叶数是n，石头数目是m。如果m是0，那么最多可以允许 n + 1 个青蛙 展开全文
去ta的博客 赞 (0) 回复(0) 收起
头像 算法妙妙屋
发表于 2020-05-12 23:02:57
设是能过河的青蛙的数量，为石墩的数量，为荷叶的数量。则。这是比较显然的，让青蛙在每个荷叶上一只，再让一只跳到对面，荷叶上的青蛙然后跳到对面。对于, 我们先河对岸的落脚点，将一个河墩视为对岸，则，最多能跳个青蛙过去。此时还剩下个河墩，如法炮制，会有 为什么会多一个呢，因为当所有石墩都占满了青蛙后，我们 展开全文
去ta的博客 赞 (0) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”