hdu 1207 汉诺塔II (DP+递推)
时间:2022-04-14 16:44
汉诺塔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时有溢出,稍稍处理一下即可。
代码:
hdu 1207 汉诺塔II (DP+递推),布布扣,bubuko.com