汉诺塔II (DP+递推)"/>
hdu 1207 汉诺塔II (DP+递推)
汉诺塔II
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4529 Accepted Submission(s): 2231
Gardon是个怕麻烦的人(恩,就是爱偷懒的人),很显然将64个圆盘逐一搬动直到所有的盘子都到达第三个柱子上很困难,所以Gardon决定作个小弊,他又找来了一根一模一样的柱子,通过这个柱子来更快的把所有的盘子移到第三个柱子上。下面的问题就是:当Gardon在一次游戏中使用了N个盘子时,他需要多少次移动才能把他们都移到第三个柱子上?很显然,在没有第四个柱子时,问题的解是2^N-1,但现在有了这个柱子的帮助,又该是多少呢?
Input 包含多组数据,每个数据一行,是盘子的数目N(1<=N<=64)。
Output 对于每组数据,输出一个数,到达目标需要的最少的移动数。
Sample Input 1 3 12
Sample Output 1 5 81
Author Gardon
Source Gardon-DYGG Contest 2
Recommend JGShining | We have carefully selected several similar problems for you: 1996 1995 2077 2184 2511
这题想了挺久的,后来才知道要用DP的思想去推。
dp思想:
对于每一个n,可以由i个四根柱子的解加上n-i个三个柱子的解。要把n个盘中的i个移到另一根柱子,需要ans[i]步,再移到目标柱子也需要ans[i]步;而剩下的n-i个盘
要从三根柱子中移到其中的目标柱子要2^(n-i)-1步。故对于每一个n,枚举i=(0,n-1)的情况,最小值为最优解。
注意当n==64时有溢出,稍稍处理一下即可。
代码:
1 //0MS 272K 613 B C++ 2 #include<stdio.h> 3 #include<math.h> 4 __int64 ans[65]={0,1,3,5}; 5 __int64 Min(__int64 a,__int64 b) 6 { 7 return a<b?a:b; 8 } 9 void init() 10 { 11 for(int i=4;i<65;i++){ 12 ans[i]=(__int64)pow(2.0,1.0*i)-1; 13 //printf("**%I64d\n",ans[i]); 14 for(int j=1;j<i;j++){ 15 if(i==64 && j==1) continue; //防止溢出得不到结果 16 __int64 temp=2*ans[j]; 17 temp+=(__int64)pow(2.0,1.0*(i-j))-1; 18 ans[i]=Min(temp,ans[i]); 19 } 20 } 21 } 22 int main(void) 23 { 24 int n; 25 init(); 26 while(scanf("%d",&n)!=EOF) 27 { 28 printf("%I64d\n",ans[n]); 29 } 30 return 0; 31 }
转载于:.html
更多推荐
hdu 1207 汉诺塔II (DP+递推)
发布评论