记录编号	168082	评测结果	AAAWWWWWWA
题目名称	[NOIP 2007]矩阵取数游戏	最终得分	40
用户昵称	devil	是否通过	未通过
代码语言	C++	运行时间	0.288 s
提交时间	2015-06-30 20:24:32	内存使用	23.74 MiB

#include <cstdlib>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <vector>
#include <stack>
#include <map>
#include <ctime>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
const int maxn=100010;
const int maxm=85;
const int MAX_INT=0x7fffffff;
const int max_int=0x7ffffff;
const int mod=99999997;

struct hp
{
    int num[10];
    hp() {memset(num,0,sizeof(num));num[0]=1;}
    void print()
    {
        printf("%d",num[num[0]]);
        for(int i=num[0]-1;i>0;i--)
            printf("%.4d",num[i]);
        printf("\n");
    }
} two_pow[maxm];

bool operator < (hp a,hp b)
{
    if(a.num[0]==b.num[0])
    {
        for(int i=a.num[0];i>0;i--)
        {
            if(a.num[i]==b.num[i]) continue;
            else return a.num[i]<b.num[i];
        }
    }
    return a.num[0]<b.num[0];
}

hp operator + (hp a,hp b)
{
    hp c;c.num[0]=max(a.num[0],b.num[0]);
    for(int i=1;i<=c.num[0];i++)
    {
        c.num[i]+=(a.num[i]+b.num[i]);
        if(c.num[i]>=10000)
        {
            c.num[i+1]+=c.num[i]/10000;
            c.num[i]%=10000;
        }
    }
    while(c.num[c.num[0]+1]!=0) c.num[0]++;
    while(c.num[c.num[0]]==0&&c.num[0]>1) c.num[0]--;
    return c;
}

hp operator * (hp a,int b)
{
    for(int i=1;i<=a.num[0];i++)
    {
        a.num[i]*=b;
        if(a.num[i]>=10000)
        {
            a.num[i+1]+=a.num[i]/10000;
            a.num[i]%=10000;
        }
    }
    while(a.num[a.num[0]+1]!=0) a.num[0]++;
    while(a.num[a.num[0]]==0&&a.num[0]>1) a.num[0]--;
    return a;
}

hp ans;
int a[maxm];
hp f[maxm][maxm][maxm];

int main()
{
    //freopen("data.in","r",stdin);
    //freopen("data.out","w",stdout);
    freopen("game.in","r",stdin);
    freopen("game.out","w",stdout);
    int n,m;scanf("%d%d",&m,&n);
    two_pow[0].num[1]=1;
    for(int i=1;i<=n;i++)
        two_pow[i]=two_pow[i-1]*2;
    while(m--)
    {
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        for(int i=1;i<=n;i++)
        {
            f[m][i][0]=f[m][i-1][0]+two_pow[i]*a[n-i+1];
            f[m][i][i]=f[m][i-1][i-1]+two_pow[i]*a[i];
        }
        hp t;
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=i;j++)
            {
                f[m][i][j]=max(f[m][i-1][j]+two_pow[i]*a[n+j+1-i],f[m][i-1][j-1]+two_pow[i]*a[j]);
                if(i==n) t=max(t,f[m][i][j]);
            }
        }
        t=max(t,f[m][n][0]);
        ans=ans+t;
    }
    ans.print();
    return 0;
}