记录编号	26914	评测结果	AAAAAAAAAA
题目名称	汉诺塔	最终得分	100
用户昵称	PurpleShadow	是否通过	通过
代码语言	C++	运行时间	0.539 s
提交时间	2011-07-29 16:09:25	内存使用	5.20 MiB

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=31,M=201,MOD=1e8;
struct Bigint
{
	int len,d[200];
	Bigint(const int& c=0)
	{
		memset(d,0,sizeof(d));
		len=1;d[0]=c;
	}
	void show()
	{
		printf("%d",d[len-1]);
		for (int i=len-2;i>=0;--i)
		{
			int j=MOD;
			while (j>10&&d[i]*10<j) 
			{
				putchar('0');
				j/=10;
			}
			printf("%d",d[i]);
		}
		printf("\n");
	}
};
Bigint operator*(const Bigint& a,const Bigint& b)
{
	Bigint c;
	c.len=a.len+b.len-1;
	for (int i=0;i<a.len;++i)
		for (int j=0;j<b.len;++j)
		{
			c.d[i+j+1]+=(long long)a.d[i]*b.d[j]/MOD;
			c.d[i+j]=((long long)a.d[i]*b.d[j]+c.d[i+j])%MOD;
		}
	while (c.d[c.len]) ++c.len;
	return c;
}
Bigint operator+(const Bigint& a,const Bigint& b)
{
	Bigint c;
	c.len=max(a.len,b.len);
	for (int i=0;i<c.len;++i)
	{
		c.d[i+1]+=(a.d[i]+b.d[i])/MOD;
		c.d[i]=(a.d[i]+b.d[i]+c.d[i])%MOD;
	}
	while (c.d[c.len]) ++c.len;
	return c;
}
bool operator<(const Bigint& a,const Bigint& b)
{
	if (a.len!=b.len) return a.len<b.len;
	for (int i=a.len-1;i>=0;--i)
		if (a.d[i]!=b.d[i]) return a.d[i]<b.d[i];
	return 0;
}
int n,m;
Bigint T[M],dp[N][M];
Bigint INF;
bool flag[N][M];
void init()
{
	scanf("%d%d",&n,&m);
	memset(flag,0,sizeof(flag));
	T[0]=0;INF.len=1e8;
	for (int i=1;i<=m;++i) T[i]=T[i-1]*2+1;
}
Bigint Zero=0,One=1;
const Bigint& slove(int n,int m)
{
	if (n==1||n==2&&m>1) return INF;
	if (m==0) return Zero;
	if (m==1) return One;
	if (n==3) return T[m];
	if (flag[n][m]) return dp[n][m];
	dp[n][m]=INF;
	for (int k=1;k<m;++k)
			dp[n][m]=min(dp[n][m],2*slove(n,k)+slove(n-1,m-k));
	flag[n][m]=1;
	return dp[n][m];
}
int main()
{
freopen("ionah.in","r",stdin);
freopen("ionah.out","w",stdout);
	init();
	Bigint Ans=slove(n,m);
	Ans.show();
	return 0;
}