本文主要是介绍【递推】【DP】-HDU-1207-汉诺塔②，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1207
题目描述：四柱汉诺塔
解题思路：开始想了方程 f [ n ] = 2 * f [n - 2] + 3和 f [ n ] = 2 * f [n - 3] + 7。结果都不对，很郁闷，纠结半天之后，上网查攻略去了，啊！我就差一点了，但也是差了最为关键的一步！ 正确的方程应该是： f [ n ] = min ( 2 * f [n - x] + g ( x ) )。1 <= x < n， 不多解释了，就是这么回事，题目的数据给到 n 为64，long long 爆掉了，因为只比 long long 最大值大了一点肯定是负数，并且又不可能是答案，我按负数特殊处理了一下，AC。
这题的方程应该很有启发意义。。扩展了对DP的认识。
AC代码：
#include <iostream>
#include <algorithm>using namespace std;long long f[70];long long g(int x)
{long long i,ans=1;for(i=1;i<=x;i++)ans*=2;return ans-1;
}int main()
{int N,i,j;f[0]=0;f[1]=1;f[2]=3;f[3]=5;for(i=4;i<=64;i++){long long ans;for(j=1;j<i;j++){if(j==1)ans=2*f[i-j]+g(j);if(2*f[i-j]+g(j)<ans&&2*f[i-j]+g(j)>0)ans=2*f[i-j]+g(j);}f[i]=ans;}while(cin>>N){cout<<f[N]<<endl;}return 0;
}
这篇关于【递推】【DP】-HDU-1207-汉诺塔②的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
