记录编号	124679	评测结果	AAAAAAAAAA
题目名称	[NOIP 2007]矩阵取数游戏	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.569 s
提交时间	2014-10-05 11:14:47	内存使用	0.59 MiB

#include <cctype>
#include <cstdio>
#define MOD 10000
using namespace std;
FILE *in = fopen("game.in","r");
FILE *out = fopen("game.out","w");
int M[81][81]={0}, n, m;
inline void getint(int &k){
	char c = fgetc(in);
	while(!isdigit(c))c = fgetc(in);
	k = c - '0';
	while(isdigit(c = fgetc(in)))
		k = k * 10 + c - '0';
}
struct big
{
    int num[10], len;
    big() { len = 1;num[0]=0; }
    big(int k) {
        len = 1, num[0]=k % MOD, k/=MOD;
        while(k)
            num[len++] = k % MOD, k /= MOD;
    }
    big& operator+=(const big& b) {
        int m=0,i;
        for(i=0;i<len || i<b.len || m;++i) {
            if(i<len) m += num[i];
            if(i<b.len) m += b.num[i];
            num[i] = m % MOD;
            m /= MOD;
        }
        if(i > len)len = i;
        return *this;
    }
    big operator +(const big& b) {
        big ans = *this;ans += b;
        return ans;
    }
    big operator *(int b)const {
        big ans = 0,k = *this;
        while(b) {
            if(b&1)ans += k;
            k += k;
            b >>= 1;
        }
        return ans;
    }
    bool operator >(const big& b)const {
        if(len!=b.len)return len > b.len;
        int i = len;
        while(--i>=0)
            if(num[i]!=b.num[i])return num[i] > b.num[i];
        return 0;
    }
}s[81][81];
int main()
{
    int i,j,t;
    getint(n),getint(m);
    big Ans, po2[81]={1};
    for(i=1;i<=m;++i)
        po2[i] = po2[i-1]*2;
    for(i=0;i<n;++i)
        for(j=0;j<m;++j)
            getint(M[i][j]);
    for(t=0;t<n;++t) {
        big temp,ans;
        s[0][m] = 0;
        for(j = m-1;j>=0;--j)
            s[0][j] = s[0][j+1] + po2[m-j] * M[t][j];
        ans = s[0][0];
        for(i = 1;i <= m;++i)
            s[i][m] = s[i-1][m] + po2[i] * M[t][i-1];
        if(s[m][m] > ans)ans = s[m][m];
        for(i = 1;i < m;++i) {
            for(j = m-1;j>=i;--j) {
                if(s[i-1][j]+po2[m+i-j]*M[t][i-1] > s[i][j+1]+po2[m+i-j]*M[t][j])
                    s[i][j] = s[i-1][j]+po2[m+i-j]*M[t][i-1];
                else s[i][j] = s[i][j+1]+po2[m+i-j]*M[t][j];
            }
            if(s[i][i] > ans)ans = s[i][i];
        }
        Ans += ans;
    }
    i = Ans.len;
    fprintf(out,"%d",Ans.num[--i]);
    while(i)
        fprintf(out,"%04d",Ans.num[--i]);
    return 0;
}