POJ 1958 Strange Towers of Hanoi [dp]

タイトル:
ハンノッタ問題.
4つの柱に変更され、解法はすでにテーマに与えられている.
考え方:
実は2つの状態方程式です.
dp3[i]=2*dp3[i-1]+1;
dp4[i]=Min(dp4[i],2*dp4[k]+dp3[i-k]);
ps:linuxの下のcsdnブログの編集はwindowsの下のよりずっときれいだと思います.

#include<iostream>
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define Max(a,b) ((a)>(b)?(a):(b))
#define Min(a,b) ((a)<(b)?(a):(b))
using namespace std;
const int N=15;
const int inf=(1<<30);
int n,m;
int dp3[N];
int dp4[N];
void solve()
{
	n=12;
	dp3[1]=1;
	dp4[1]=1;
	for(int i=2;i<=n;i++)
	{
		dp3[i]=2*dp3[i-1]+1;
		dp4[i]=inf;
	}
	for(int i=2;i<=n;i++)
	{
		for(int k=1;k<i;k++)
		{
			dp4[i]=Min(dp4[i],2*dp4[k]+dp3[i-k]);
		}
	}
	for(int i=1;i<=n;i++)
	  printf("%d
",dp4[i]);
}
int main()
{
	solve();
	return 0;
}