青蛙过河_牛客博客

题意：类似汉诺塔问题，但是需要分析细节。
题解： 荷叶数为 $m$ ，石墩数为 $n$ 。
当 $n=0$ ，那么最多先 $m$ 个到荷叶，第 $m+1$ 个到终点。
当 $n=1$ ，那么最多 $m+1$ 个到荷叶和石墩，然后荷叶上的 $m$ 个再到石墩。情况转换为 $n=0$ 的情况，两者相加即 $(m+1)\times2$
当 $n=2$ ，那么最多先 $m+1$ 个到荷叶和石墩1，然后荷叶上的到石墩1，之后再有 $m+1$ 个到荷叶和石墩2，然后这 $m+1$ 个到石墩1。情况转换为了 $n=1$ 的情况，两者相加为 $(m+1)\times2^2$ 。注意：此时不能先有 $m+2$ 个到石墩1和石墩2，然后都到石墩1，之后再有 $m+1$ 个到石墩2和荷叶，再到石墩1，这样的话即使后面可以按照 $n=1$ 的情况走下去，但是因为全程要符合青蛙的高低顺序，那么就要使得石墩1的最面的青蛙解放，但是解放时，只能给最上面的 $m+1$ 个释放到石墩2，然后只剩 $m+1$ 个石墩+荷叶但是有 $m+2$ 个青蛙，无法释放最底的青蛙，故不行。
那么通式就是 $(m+1)\times2^n$ .

代码：

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n, m;
int main()
{
    scanf("%lld%lld", &n, &m);
    printf("%lld\n", (1ll << n) * (m + 1));
    return 0;
}