比赛 |
20110728 |
评测结果 |
AAWWWWAAAA |
题目名称 |
汉诺塔 |
最终得分 |
60 |
用户昵称 |
PurpleShadow |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-07-28 10:48:36 |
显示代码纯文本
#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) 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;
}