| 比赛 | 
    20110728 | 
    评测结果 | 
    AAAAAAAAAA | 
    | 题目名称 | 
    汉诺塔 | 
    最终得分 | 
    100 | 
    | 用户昵称 | 
    .Xmz | 
    运行时间 | 
    0.000 s  | 
    | 代码语言 | 
    C++ | 
    内存使用 | 
    0.00 MiB  | 
    | 提交时间 | 
    2011-07-28 09:04:15 | 
显示代码纯文本
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <cstdio>
using namespace std;
int n,m;
long long f[31][201];
struct bignumber
{
	int x[201];
	void print()
	{
		bool yy=false;
		for (int i=200;i>0;i--)
		if (x[i]!=0 || yy)
		{
			yy=true;
			printf("%d",x[i] - (i==1 ? 1 : 0) );
		}
		printf("\n");
	}
}X;
bignumber operator + (bignumber &a,bignumber &b)
{
	bignumber c;
	memset(c.x,0,sizeof(c.x));
	int delta=0;
	for (int i=1;i<=200;i++)
	{
		c.x[i]=a.x[i]+b.x[i]+delta;
		delta=c.x[i]/10;
		c.x[i]%=10;
	}
	return c;
}
int main()
{
	freopen("ionah.in","r",stdin);
	freopen("ionah.out","w",stdout);
	scanf("%d%d",&n,&m);
	if (n==3)
	{
		X.x[1]=1;
		for (int i=1;i<=m;i++) X=X+X;
		X.print();
	}
	if (n!=3)
	{
		for (int i=3;i<=n;i++)
		for (int j=1;j<=m;j++)
		{
			if (i==3) f[i][j]=((long long)1<<min(60,j))-1;
			else if (j==1) f[i][j]=1;
			else
			{
				for (int k=j-1;k>=1;k--)
				{
					if ( k==j-1 || f[i][j]>2*f[i][k]+f[i-1][j-k] ) 
					f[i][j]=2*f[i][k]+f[i-1][j-k];
				}
			}
		}
		printf("%lld\n",f[n][m]);
	}
	return 0;
}