JZOJ 6797. 【2014广州市选day2】hanoi

题目大意

没什么，就是把原本汉诺塔的三根柱子改成四根，求最少步数
其中 (1 leq n leq 1000)

思路

设 (f_{i}) 表示四根柱子中把其中一根 (i) 个移到另一根的最小步数
(g_i) 类似，改成三根柱子
那么 (f_i = min(g_j * 2 + f_{i-j-1} * 2 + 1)) ， (g_j = g_{j-1} * 2 + 1)
就是把一根柱子上的若干个分成上下两份，先整体移动上面一份，再移动另一份，统计贡献
似乎是 (O(n^2)) 的（可过）
其实我们发现 (g) 增长得很快
而我们最终的答案 (f_n)，若 (n=1000)，那么 (f_n) 是不会爆出 (2^{60}) 的
所以 (g) 只要更新到第 (60) 个左右就行了
为了代码显得更通俗易懂
所以贴个 (O(n^2)) 的，顺手改改就成了

(Code)

#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
typedef long long LL;

int n;
LL f[1005] , g[1005] , INF = 1e18;

int main()
{
	freopen("hanoi.in" , "r" , stdin);
	freopen("hanoi.out" , "w" , stdout);
	scanf("%d" , &n);
	memset(f , 60 , sizeof f);
	f[0] = 0 , f[1] = 1 , f[2] = 3;
	g[0] = 0 , g[1] = 1 , g[2] = 3;
	for(register int i = 3; i <= n; i++)
	{
		g[i] = g[i - 1] * 2 + 1;
		if (g[i] > INF) g[i] = INF;
		for(register int j = 0; j < i; j++) 
			f[i] = min(f[i] , g[j] * 2 + f[i - j - 1] * 2 + 1);
	}
	printf("%lld" , f[n]);
}