记录编号	319532	评测结果	AAAAAAAAAA
题目名称	[NOIP 2007]矩阵取数游戏	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.289 s
提交时间	2016-10-10 19:21:09	内存使用	2.24 MiB

#include<cstdio>
#include<cstring>
const int maxn=100;
int a[maxn];
int max(int a,int b){
    return a>b?a:b;
}
struct ll{
    int num[50];int len;
    ll(){
        memset(num,0,sizeof(num));len=0;
    }
    ll(int x){
        memset(num,0,sizeof(num));len=1;
        num[1]=x;
        while(num[len]>=10){
            num[len+1]=num[len]/10;
            num[len]%=10;
            ++len;
        }
    }
    ll operator +(const ll &B)const{
        ll C;
        C.len=max(len,B.len);
        for(int i=1;i<=C.len;++i){
            C.num[i]=num[i]+B.num[i];
        }
        for(int i=1;i<=C.len;++i){
            if(C.num[i]>=10){
                C.num[i+1]++;
                C.num[i]-=10;
                if(i==C.len)C.len++;
            }
        }
        return C;
    }
    ll operator *(int x)const{
        ll B;
        B.len=len;
        for(int i=1;i<=len;++i){
            B.num[i]=num[i]*2;
        }
        for(int i=1;i<=B.len;++i){
            if(B.num[i]>=10){
                B.num[i+1]+=B.num[i]/10;
                B.num[i]%=10;
                if(i==B.len)B.len++;
            }
        }
        return B;
    }
    bool operator >(const ll &B)const{
        if(len!=B.len)return len>B.len;
        else{
            for(int i=len;i>=1;--i){
                if(num[i]!=B.num[i]){
                    return num[i]>B.num[i]; 
                }
            }
            return false;
        }
    }
    void output(){
        for(int i=len;i>=1;--i){
            printf("%d",num[i]);
        }
    }
}f[maxn][maxn];
ll ans;
int main(){
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    int n,m;scanf("%d%d",&n,&m);
    for(int i=1;i<=n;++i){
        for(int i=1;i<=m;++i){
            scanf("%d",a+i);
        }
        memset(f,0,sizeof(f));
        for(int i=1;i<=m;++i)f[i][i]=ll(a[i]);
        ll tmp;int j;
        for(int k=1;k<m;++k){
            for(int i=1;i+k<=m;++i){
                j=i+k;
                f[i][j]=f[i+1][j]*2+f[i][i];
                tmp=f[i][j-1]*2+f[j][j];
                if(tmp>f[i][j])f[i][j]=tmp; 
            }
        }
        ans=ans+f[1][m];
    }
    ans=ans*2;
    ans.output();//while(1);
    fclose(stdin);fclose(stdout);
    return 0;
}