首页 > 代码库 > hdu1207 汉诺塔II 简单dp
hdu1207 汉诺塔II 简单dp
本文出自:http://blog.csdn.net/svitter
题意:汉诺塔,多了一根柱子,问你寻找最快的移动次数。
dp [ n ] = dp [ n - j ] * 2 + pow( 2, j ) - 1;
就是把j个汉诺塔移到一根上dp[ n - j ],然后就是普通的汉诺塔问题,即2^n - 1次移动,
然后把剩下的移动过去dp [ n - j ].
注意pow(2, j )可能超出long long int范围。写二的次方的时候也可用移位算法。
#include <iostream> #include <cstdio> #include <string.h> using namespace std; #define lln long long int #define min(a, b) a < b ? a : b lln dp[65]; //for pow lln temp, ans, tt; lln pow(lln x, lln n) { temp = x, ans = 1, tt = n; while(tt) { if(tt &1) ans = (ans * temp); temp = temp * temp; tt = tt >> 1; } return ans; } lln pow2(lln x) { lln i = 0; lln j = 1; while(i < x) { j <<= 1; i++; } return j; } void init() { memset(dp, 0x3f, sizeof(dp)); dp[1] = 1; dp[2] = 3; dp[3] = 5; lln tmp; for(int i = 4; i <= 64; i++) for(int j = 1; j < i; j++) { tmp = pow(2, j); if(tmp > dp[i]) break; dp[i] = min(2 * dp[i - j] + tmp - 1, dp[i]); } } void ace() { int t; init(); while(~scanf("%d", &t)) printf("%lld\n", dp[t]); } int main() { ace(); return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。