【2014广州市选day2】hanoi

题目大意

你对经典的hanoi塔问题一定已经很熟悉了。有三根柱子，n个大小不一的圆盘，要求大盘不能压在小盘上，初始时n个圆盘都在第一根柱子上，最少要多少步才能挪到最后一根柱子上？
现在我们来将hanoi塔扩展一下，由三根柱子扩展到四根柱子，其余规则不变。

解题思路

其实我们可以把四根柱子转化为三根，对于(n)个盘子，我们可以把它分为两部分，上半部分(x)个，下半部分(y)个

考虑把(x)个移到另一个柱子
再把(y)移到另一个柱子
移动(x)是在四个柱子上完成的，移完(y)后，还要把(x)移动到(y)上，所以贡献是(2f_x)

因为移动完(x)有一个柱子被占了，所以移动(y)是在三个柱子上完成的，贡献是(2^y - 1)

所以递推式是
(f_i = min(2f_x+2^y - 1))

Code

#include<cstdio>
#include<algorithm>
using namespace std;
long long f[1005];
int n;

long long ksm(long long x,long long y)
{
	long long res = 1;
	while (x)
	{
		if (x & 1) res *= y;
		y *= y;
		x /= 2;
	}
	return res;
}
int main()
{
	scanf("%d",&n);
	f[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		f[i] = ksm(1,2) - (long long)1 + 2 * f[i - 1];
		for (int j = 2; j < min(i,60); j++)
		f[i] = min(f[i],ksm(j,2) - (long long)1 + 2 * f[i - j]);
	}
	printf("%lld
",f[n]);	
}