比赛 20110728 评测结果 AAAAAAAAAA
题目名称 汉诺塔 最终得分 100
用户昵称 Pom 运行时间 0.000 s
代码语言 C++ 内存使用 0.00 MiB
提交时间 2011-07-28 11:13:10
显示代码纯文本
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>

using namespace std;

const int MAXN=300;
const int H=1000000;
const int oo=100000000;

struct number
{
	int a[1050],len;
	void cls()
	{
		for (int k=0;k<1050;k++)
			a[k]=0;
		len=0;
	}
}f[31][MAXN],t;

int n,m,i,j,k,F[40][300];

void cal(number *X,number *Y)
{
	number A=*X,B=*Y;
	for (int i=1;i<=A.len+1;i++)
	{
		A.a[i]=A.a[i]*2+A.a[i-1]/H;
		A.a[i-1]%=H;
	}
	if (A.a[A.len+1]) ++A.len;
	t.cls();
	t.len=max(A.len,B.len);
	for (int i=1;i<=t.len+1;i++)
	{
		t.a[i]=A.a[i]+B.a[i]+t.a[i-1]/H;
		t.a[i-1]%=H;
	}
	if (t.a[t.len+1]) ++t.len;
}

bool cmp()
{
	if (f[i][j].len>t.len) return true;
	if (f[i][j].len<t.len) return false;
	for (int x=t.len;x>=1;x--)
	{
		if (t.a[x]>f[i][j].a[x]) return false;
		if (t.a[x]<f[i][j].a[x]) return true;
	}
	return false;
}

int main()
{
	freopen("ionah.in","r",stdin);
	freopen("ionah.out","w",stdout);
	scanf("%d%d",&n,&m);
	if (n>3)
	{
		for (i=1;i<=n;i++) F[i][1]=1;
		for (i=2;i<MAXN;i++) F[2][i]=oo;
		for (i=3;i<=n;i++)
			for (j=2;j<=m;j++)
			{ 
				F[i][j]=oo;
				for (k=1;k<j;k++)
					F[i][j]=min(F[i][j],F[i][k]*2+F[i-1][j-k]);
			}
		cout<<F[n][m]<<endl;
		return 0;
	}
	for (i=2;i<=n;i++) f[i][1].len=f[i][1].a[1]=1;
	for (i=2;i<MAXN;i++)
	{
		f[2][i].len=1000;
		f[2][i].a[1000]=1;
	}
	for (i=3;i<=n;i++)
		for (j=2;j<=m;j++)
		{
			f[i][j].len=1000;
			f[i][j].a[1000]=1;
			for (k=1;k<j;k++)
			{
				cal(f[i]+k,f[i-1]+j-k);
				if (cmp()) f[i][j]=t;
			}
		}
	for (i=f[n][m].len;i>0;i--)
		printf("%d",f[n][m].a[i]);
	printf("\n");
	return 0;
}