P1244 [NOI2000] 青蛙过河 题解

[AC记录先奉上](https://www.luogu.com.cn/record/46509798) 然后是[题目传送门](https://www.luogu.com.cn/problem/P1244) 这道题首先要注意A和B都是石墩，需要小的在大的上面 石墩可以理解成汉诺塔 首先我们看h=0的情况 显然，让k只青蛙先到k个荷叶上就位，再让1只青蛙去b，答案就是k+1 h=1 先让k只青蛙到荷叶上，然后让一只青蛙去1号石墩，再让荷叶上的k只青蛙来到1号石墩，这样1号石墩上就有k+1只青蛙了 现在可以把1号石墩当成满了，因为下一个青蛙编号会大，而要从顶端放，所以放不了 这是就是h=0的情况了，及最终答案为：h=0+(k+1)=(k+1)+(k+1) h=2 先让1号石墩上有k+1个青蛙，过程与上面一样，再让2号石墩上有k+1只青蛙，过程与上一次一样，再让一号石墩的青蛙的k只青蛙去荷叶上，让第k+1只去二号石墩，再让荷叶上的k只青蛙去2号石墩，这时就可以想成h=1了，所以答案为：h=1+(k+1+k+1)=(k+1+k+1)+(k+1+k+1) 余下同理 我们可以推导出公式，h每＋1，就是上一个的结果乘2 # so,上代码！ ```cpp #include<bits/stdc++.h> using namespace std; int a[20][1000]; int main() { int n,m,i; scanf("%d%d",&n,&m); a[0][m]=m+1;//n=0是答案是m+1 for(i=1;i<=n;i++) { a[i][m]=a[i-1][m]*2;//上一个结果*2 } printf("%d",a[n][m]); //printf("%d",(m+1)*(n<<1));//其实就是2的n次方*(m+1) return 0; } ```