矩阵取数游戏 NOIP 2007

//矩阵取数游戏 (NOIP2007)
//动态规划 高精度
#include<stdio.h>
#include<algorithm>
#include<string.h>
using namespace std;
const int maxn=;
const int maxm=;
const int maxl=;
int N,M;
int a[maxn];
int DP[maxn][maxm][maxl];
int ys[maxn][maxl];
int ans[maxl];
int tmp[maxl];
void Multi(int *x,int *y,int z)
{
memset(tmp,,sizeof(tmp));
tmp[]=y[];
for(int i=;i<=tmp[];i++)
{
tmp[i]=y[i]*z;
}
for(int i=;i<=tmp[];i++)
{
tmp[i+]+=tmp[i]/;
tmp[i]%=;
}
while(tmp[tmp[]+])
{
tmp[]++;
tmp[tmp[]+]+=tmp[tmp[]]/;
tmp[tmp[]]%=;
}
for(int i=;i<;i++)x[i]=tmp[i];
return ;
}
void Add(int *x,int *y,int *z)
{
memset(tmp,,sizeof(tmp));
if(y[]>z[])tmp[]=y[];
else tmp[]=z[];
for(int i=;i<=tmp[];i++)
{
tmp[i]=y[i]+z[i];
}
for(int i=;i<=tmp[];i++)
{
tmp[i+]+=tmp[i]/;
tmp[i]%=;
}
if(tmp[tmp[]+])tmp[]++;
for(int i=;i<;i++)x[i]=tmp[i];
return ;
}
bool Max(int *x,int *y)
{
if(x[]>y[])return ;
else if(y[]>x[])return ;
else
{
for(int i=x[];i>=;i--)
{
if(x[i]>y[i])return ;
else if(x[i]<y[i])return ;
}
}
return ;
}
int main()
{
scanf("%d %d",&N,&M);
ys[][]=;
ys[][]=;
for(int i=;i<=M;i++)
{
Multi(ys[i],ys[i-],);
}
ans[]=;ans[]=;
for(int i=;i<=N;i++)
{
for(int j=;j<=M;j++)
{
scanf("%d",&a[j]);
Multi(DP[j][j],ys[M],a[j]);
}
for(int k=;k<=M;k++)
{
for(int x=;x<=M-k+;x++)
{
int y=x+k-;
int xm[],ym[],cm[];
Multi(cm,ys[M-k+],a[x]);
Add(xm,cm,DP[x+][y]);
Multi(cm,ys[M-k+],a[y]);
Add(ym,cm,DP[x][y-]);
if(Max(xm,ym))
{
memcpy(DP[x][y],xm,sizeof(int)*);
}
else
{
memcpy(DP[x][y],ym,sizeof(int)*);
}
}
}
Add(ans,ans,DP[][M]);
}
printf("%d",ans[ans[]]);
for(int i=ans[]-;i>=;i--)
{
printf("%05d",ans[i]);
}
printf("\n");
return ;
}