比赛 |
20110728 |
评测结果 |
WWAAAAWWAW |
题目名称 |
汉诺塔 |
最终得分 |
50 |
用户昵称 |
苏轼 |
运行时间 |
0.000 s |
代码语言 |
C++ |
内存使用 |
0.00 MiB |
提交时间 |
2011-07-28 11:17:28 |
显示代码纯文本
#include <cstdio>
#include <cassert>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN=35,MAXM=205,MAXL=100;
const int oo=~0u>>2;
struct High;
ostream & operator << (ostream &out,const High &a);
struct High
{
int len,a[MAXL];
bool operator >= (const High &b) const
{
if (len!=b.len)
return len>b.len;
for(int i=len-1;i>=0;i--)
if (a[i]!=b.a[i])
return a[i]>b.a[i];
return true;
}
bool operator != (const int &x) const
{
assert(x==oo);
return len!=MAXL;
}
High operator + (const High &b) const
{
High c;
c.len=max(len,b.len);
for(int i=0;i<c.len;i++)
{
c.a[i]+=a[i]+b.a[i];
if (c.a[i]>=10)
{
c.a[i]-=10;
c.a[i+1]++;
}
}
if (c.a[c.len]!=0)
c.len++;
// cerr<<*this<<" + "<<b<<" = "<<c<<endl;
return c;
}
High operator * (const int &x) const
{
assert(x==2);
High c=*this;
for(int i=0;i<c.len;i++)
c.a[i]*=x;
for(int i=0;i<c.len;i++)
if (c.a[i]>=10)
{
c.a[i]-=10;
c.a[i+1]++;
}
if (c.a[c.len]!=0)
c.len++;
// cerr<<*this<<" * "<<x<<" = "<<c<<endl;
return c;
}
High(int x)
{
memset(a,0,sizeof(a));
if (x!=oo)
{
assert(x==0 || x==1);
len=1,a[0]=x;
}
else
{
assert(x==oo);
len=MAXL;
}
}
High()
{
len=1;
memset(a,0,sizeof(a));
}
};
ostream & operator << (ostream &out,const High &a)
{
for(int i=a.len-1;i>=0;i--)
out<<a.a[i];
return out;
}
int N,M;
High d[MAXM],g[MAXN][MAXM];
int maxdep;
int main()
{
freopen("ionah.in","r",stdin);
freopen("ionah.out","w",stdout);
cin>>N>>M;
maxdep=N-2;
for(int i=0;i<=maxdep;i++)
for(int j=0;j<=M-1;j++)
g[i][j]=oo;
g[0][0]=0;
d[1]=1;
for(int i=1;i<=M;i++)
{
if (i!=1)
d[i]=g[maxdep][i-1]*2+1;
for(int k=0;k<maxdep;k++)
for(int j=0;j+i<=M-1;j++)
if (g[k][j]!=oo)
{
High t=g[k][j]+d[i];
if (!(t>=g[k+1][j+i]))
g[k+1][j+i]=t;
if (!(g[k][j]>=g[k+1][j]))
g[k+1][j]=g[k][j];
}
}
cout<<d[M]<<endl;
return 0;
}