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

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
const int MAXN=80+10,BASE=1e4;
struct BIG{
	int a[100],s;
	BIG(){memset(this,0,sizeof(*this));}
	BIG(int x){
		a[1]=x;
		s=1;
	}
}f[MAXN][MAXN];
BIG operator+(const BIG& a,const BIG& b){
	BIG c;
	c.s=max(a.s,b.s);
	int i,g;
	for(g=0,i=1;i<=c.s;i++){
		c.a[i]=a.a[i]+b.a[i]+g;
		g=c.a[i]/BASE;
		c.a[i]%=BASE;
	}
	while(g) c.a[++c.s]=g%BASE,g/=BASE;
	return c;
}
BIG operator*(const BIG& a,int b){
	BIG c;
	c.s=a.s;
	int i,g;
	for(g=0,i=1;i<=c.s;i++){
		c.a[i]=a.a[i]*b+g;
		g=c.a[i]/BASE;
		c.a[i]%=BASE;
	}
	while(g) c.a[++c.s]=g%BASE,g/=BASE;
	return c;
}
bool operator<(const BIG& a,const BIG& b){
	if(a.s<b.s) return true;
	else if(a.s>b.s) return false;
	else for(int i=a.s;i>=1;i--) {
		if(a.a[i]<b.a[i]) return true;
		else if(a.a[i]>b.a[i]) return false;
	}
	return false;
} 
ostream& operator<<(ostream& os,const BIG& a){
	printf("%d",a.a[a.s]);
	for(int i=a.s-1;i>=1;i--) printf("%04d",a.a[i]);
	return os;
}
int n,m,w[MAXN][MAXN];
BIG ans,fac2[MAXN];
int main(){
	freopen("game.in","r",stdin);
	freopen("game.out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cin>>w[i][j];
	fac2[0]=1;
	for(int i=1;i<=m;i++) fac2[i]=fac2[i-1]*2;
	for(int k=1;k<=n;k++){
		memset(f,0,sizeof(f));
		BIG now;
		int* a=w[k];
		for(int i=1;i<=m;i++) {
			for(int j=0;j<=i;j++) {
				f[i][j]=f[i-1][j]+fac2[i]*a[m-i+j+1];
				if(j-1>=0) {
					//f[i][j]=max(f[i-1][j-1]+fac2[i]*a[j],f[i][j]);
					BIG t=f[i-1][j-1]+fac2[i]*a[j];
					if(f[i][j]<t) f[i][j]=t;
				}
			}
		}
		for(int i=0;i<=m;i++) if(now<f[m][i]) now=f[m][i];
		ans=ans+now;
	}
	cout<<ans;
}