比赛 |
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;
}