hdoj 1207 汉诺塔II dp 动态规划
题目描述: http://acm.hdu.edu.cn/showproblem.php?pid=1207(中文)
题目分析:
以下思路转自:http://yxq0620.blog.163.com/blog/static/4449439220102245168595/
初看很难,理解了会发现真的很简单的...
不明白的建议看一下 http://poj.org/problem?id=1958这题,里面有dp 的思路.
如果不明白就继续看吧.
dp表示 将n个盘子通过4根柱子移动到目的柱子的最小的步数, f( i )表示 把 i个盘子通过 3根柱子移动到目的柱子的最小步数,f(i) 题目已经给出.
dp[ n ] =min(dp[ i ] * 2 + f(n - i));
dp可以通过状态转移方程写出来,或许有的人看了状态转移方程,觉得很难想到,或者看不懂这个方程的意思,我来说说我自己的理解...
要将n各盘子移动到目的的柱子, 而要求最小的步数,所以先 将上面的k个盘子 通过4根柱子移动到 不是目的柱子和开始柱子的另外两个柱子的其中一个. 然后, 现在除了开始的柱子以外,剩下空的柱子就只有2根了. 所以就将剩下的 n-k个柱子通过3根柱子来移动到目地柱子, 最后 将开始 上面的k各盘子 通过4根柱子移动到目的柱子上面,
(1<=k<n);
所以状态转移方程就是这个样子
#include <iostream>using namespace std;int main() { unsigned long long step; unsigned long long f; f = 1; unsigned long long i,j,min,cur,t = 1; for(i = 2; i < 64; i++)//注意:只处理到i = 63 f = (t << i) - 1;//f = (int)(pow(2, i) - 1); //f = 2 * f + 1; step = 0; step = 1; step = 3; for(i = 3; i <= 64; i++) { min = 0xffffffffffffffffUUL;//UUL 表示unsigned long long, 我的g++ 不加UUL能过, 提交的时候却总是CE, 加上UUL, AC, 其实min 大于18433 就行 for(j = 1; j < i; j++) { cur = 2 * step + f; if(cur < min) min = cur; } step = min; } int n; while(cin>>n) cout<<step<<endl; return 0;}
注意:
1. 只用long long 或是 __int64 计算过程会溢出, 所以要加unsigned
2. 由于用unsigned long long, 编译器要选g++
3. 有大牛发现以下规律, 所以该题不用dp 也能AC
规律：
step=1;
step=step+2; step=step+2;(2个加2^1)
step=a+4; step=step+4; step=step+4;(3个加2^2);
…………………………………………(4个加2^3);
O(∩_∩)O~
页:
[1]