poj1958 四座塔的汉诺塔

题意：和经典三座塔的汉诺塔唯一的不同就是多了一个塔，其余规则一样；

思路：

在三经典汉诺塔中，当有n个盘子时，我们可以先把上面的n-1个盘子移动到B，然后把最下面的一个盘移动到C，最后把B上的n-1个移到C上，即是f3[n]=2*f3[n-1]+1。其实就是一个动态规划。当然最简单的就是2^n-1。这个结论可以自己证明，挺简单的。

那现在我们有四个塔，可以怎样做呢？

假设现在有n个盘子，我们可以先把k（1<=k<=n）个盘子在四塔模式下移动到B，然后不动这k个盘子，把剩下的n-k个盘子移动到D（这一步我们可以提前做，即是先求三塔模式下的n盘问题），最后再把这k个盘子在四塔模式下移动到D。动态转移方程为：

f4[n]=min(2*f4[k],f3[n-k])       (1<=k<=n)

这里k==n时，即是不通过第四个塔移动n个盘子，在上面的方程中显然是取不到的，故k可以<=n。当然写成1<=k<n也是可以的。这二者并没有上面影响。

#include<cstdio>
#include<algorithm>
using namespace std;
int f3[15], f4[15];

int main() {
	f3[1] = 1; f4[1] = 1;
	for (int i = 2; i <= 12; i++)f3[i] = 2 * f3[i - 1] + 1;

	for (int i = 2; i <= 12; i++) {
		f4[i] = 2 * f4[1] + f3[i - 1];
		for (int k = 1; k <=i; k++)
			f4[i] = min(f4[i], 2 * f4[k] + f3[i - k]);
	}
	for (int i = 1; i <= 12; i++)
		printf("%d\n",f4[i]);
	return 0;
}