【题解】POJ P1958 【Strange Towers of Hanoi】

经典的汉诺塔的升级版

四根柱子,n个盘(1\leq n\leq12)

对于三根柱子,设d[n]n盘时的最小步数,显然d[n] = 2 \times d[n-1]+1,自己模拟一下就可以得到了

对于四根柱子,设f[n]n盘时的最小步数,则:

f[n] = \min \left \{ 2 \times f[i] + d[n - i] \right \}|1\leq i < n

其中f[1] = 1;表示先把 i 个盘子在4根柱子下移动到第二根柱子,然后把 n - i 个盘子在3根柱子下移到最后一根柱子,最后把 i 个盘子在4根柱子下移到最后一根柱子,考虑所有的 i 取最小值。

#include<cstdio>
#include<vector>
#include<algorithm>

namespace OI{
	using std::vector;
	using std::sort;
}
using namespace OI;

const int INF = 0x3f3f3f3f;

void init(vector<int> &d,vector<int> &f){
	for(int i = 0;i <= 12;i++){
		d.push_back(INF);
		f.push_back(INF);
	}
}

int main(){
	int n = 12;
	
	vector<int> d;
	vector<int> f;
	
	init(d,f);
	
	d[0] = 0;
	for(int i = 1;i <= n;i++){
		d[i] = 2 * d[i - 1] + 1;
	}
	
	f[1] = 1;
	for(int i = 2;i <= n;i++){
		for(int j = 1;j < i;j++){
			if(f[i]>(2 * f[j] + d[i - j]))
			f[i] = 2 * f[j] + d[i - j];
		}
	}
	
	for(int i = 1;i <= n;i++){
		printf("%d\n",f[i]);
	}
	
	return 0;
}