记录编号	250459	评测结果	AAAAAAAAAA
题目名称	[NOIP 2008]传纸条	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2016-04-15 10:33:57	内存使用	1.54 MiB

#include<cstdio>
int f[120][52][52];
int p[52][52];
int max(int a,int b){
	return a>b?a:b;
}
int min(int a,int b){
	return a<b?a:b;
}
int main(){
	freopen("message.in","r",stdin);
	freopen("message.out","w",stdout);
	int m,n;scanf("%d %d",&m,&n);
	for(int i=1;i<=m;++i){
		for(int j=1;j<=n;++j){
			scanf("%d",&p[i][j]);
		}
	}
	
	for(int k=1;k<m+n-2;++k){//两个纸条 均走了k步 
		for(int i=max(1,k-n+2);i<=min(m,k+1);++i)
			for(int j=max(1,k-n+2);j<=min(m,k+1);++j){
				if(i!=j)
					f[k][i][j]=max(max(f[k-1][i-1][j],f[k-1][i-1][j-1]),\
					max(f[k-1][i][j],f[k-1][i][j-1]))+p[i][k-i+2]+p[j][k-j+2];
			//	printf("f%d %d %d==%d\n",k,i,j,f[k][i][j]);
			}
	}
	printf("%d",max(f[m+n-3][m][m-1],f[m+n-3][m-1][m]));
	fclose(stdin);fclose(stdout);
	return 0;
}