题目大意

你对经典的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\n",f[n]);	
}