题目描述: 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]表示 将n个盘子通过4根柱子移动到目的柱子的最小的步数, f( i )表示 把 i个盘子通过 3根柱子移动到目的柱子的最小步数,f(i) 题目已经给出.
dp[ n ] =min(dp[ i ] * 2 + f(n - i));
dp[n]可以通过状态转移方程写出来,或许有的人看了状态转移方程,觉得很难想到,或者看不懂这个方程的意思,我来说说我自己的理解...
要将n各盘子移动到目的的柱子, 而要求最小的步数,所以先 将上面的k个盘子 通过4根柱子移动到 不是目的柱子和开始柱子的另外两个柱子的其中一个. 然后, 现在除了开始的柱子以外,剩下空的柱子就只有2根了. 所以就将剩下的 n-k个柱子通过3根柱子来移动到目地柱子, 最后 将开始 上面的k各盘子 通过4根柱子移动到目的柱子上面,
(1<=k<n);
所以状态转移方程就是这个样子
#include <iostream> using namespace std; int main() { unsigned long long step[65]; unsigned long long f[65]; f[1] = 1; unsigned long long i,j,min,cur,t = 1; for(i = 2; i < 64; i++) //注意:只处理到i = 63 f[i] = (t << i) - 1;//f[i] = (int)(pow(2, i) - 1); //f[i] = 2 * f[i - 1] + 1; step[0] = 0; step[1] = 1; step[2] = 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[j] + f[i - j]; if(cur < min) min = cur; } step[i] = min; } int n; while(cin>>n) cout<<step[n]<<endl; return 0; }
注意:
1. 只用long long 或是 __int64 计算过程会溢出, 所以要加unsigned
2. 由于用unsigned long long, 编译器要选g++
3. 有大牛发现以下规律, 所以该题不用dp 也能AC
规律:
step[1]=1;
step[2]=step[1]+2; step[3]=step[2]+2;(2个加2^1)
step[4]=a[3]+4; step[5]=step[4]+4; step[6]=step[5]+4;(3个加2^2);
…………………………………………(4个加2^3);
O(∩_∩)O~
发表评论
-
ACM 之 Java BigInteger
2011-06-01 20:26 0Java 的大整数类在ACM 中大有用武之地 ... -
判断点是否构成多边形, 顶点连续给出
2011-05-26 14:27 0#include <cstdio> #inc ... -
poj pku 1981 Circle and Points 点与圆 位置关系
2011-05-26 11:29 1255题目描述: http://poj.org/problem?id ... -
poj 1032 Parliament 数学
2011-05-25 17:34 1205题目描述: http://poj.org/problem?i ... -
poj 1385 Lifting the Stone 多边形重心
2011-05-25 11:13 1022题目描述: http://poj.org/problem?i ... -
poj 2676 Sudoku dfs 深搜
2011-05-16 21:05 866题目描述: http://poj.org/problem?i ... -
hdoj 2064 汉诺塔III 递推
2011-05-15 22:29 877题目描述: http://acm.hdu.edu.cn/sh ... -
poj 2506 Tiling 递推
2011-05-15 11:18 899题目描述: http://poj.org/problem?i ... -
poj 2420 A Star not a Tree? 多边形 费马点
2011-05-14 18:57 1789题目描述: http://poj.org/problem?i ... -
poj 2954 Triangle Pick 定理
2011-05-14 16:36 1077题目描述: http://poj.org/problem?i ... -
poj 1012 Joseph
2011-05-10 17:42 1226题目描述:poj.org/problem?id=10 ... -
zoj 1081 Points Within 点与多边形关系
2011-05-07 17:51 1127题目描述: http://acm.zju.edu.cn/on ... -
poj 1835 宇航员
2011-05-03 17:00 792题目描述:http://poj.org/problem?id ... -
poj 2398 Toy Storage
2011-04-23 20:19 709题目描述:http://www.poj.org/proble ... -
poj 1654 Area 多边形面积
2011-04-23 20:10 888题目描述:http://poj.org/proble ... -
poj 2318 TOYS 点 直线 位置关系
2011-04-23 10:06 658题目描述:http://poj.org/problem?id= ... -
poj pku 1673 EXOCENTER OF A TRIANGLE 三角形 垂心
2011-04-09 16:41 538题目描述:http://poj.org/problem?id= ... -
pc 111303 uva 10195 The Knights Of The Round Table
2011-04-04 16:06 747题目描述:http://www.programming-cha ... -
pc 111302 uva 10180 Rope Crisis in Ropeland!
2011-04-03 20:46 830题目描述: http://www.programming-ch ... -
poj 1971 Parallelogram Counting 平行四边形个数
2011-04-03 10:05 1205题目描述:http://poj.org/problem?id= ...
相关推荐
一些HDOJ上的DP题目的小总结,但愿能帮到那些想专攻DP的人吧
HDOJ题目分类HDOJ题目分类HDOJ题目分类
ACM ICPC HDOJ1002
ACM ICPC HDOJ1001
hdoj1001标程
hdoj上的资源,代码有注释,很不错的哦
hdoj1004,解题代码,答案代码,欢迎下载
ACM ICPC HDOJ1003
ACM ICPC HDOJ1008
杭州电子科技大学hdoj1002,大整数相加问题
杭州电子科大HDOJ
c语言 最短路 是hdoj上的一个最短路问题,写的很牛
ACM ICPC HDOJ1000
hdoj解题代码,题目为1000-1050
codj,hdoj的源码(50-60题)
包括简单数学 组合数学 动态规划 贪心算法 母函数 搜索算法 组合博弈论 计算几何 等等
hdoj 2013 多校训练3标程+解题报告
HDOJ 源代码 包含几百道HDOJ题目源码
hdoj1005 Number Sequence, 杭州电子科技大学oj题目代码
杭电OJ(1000-1099) AC 代码