记录编号	350749	评测结果	AAAAAAAAAA
题目名称	219.[NOIP 2008]传纸条	最终得分	100
用户昵称	Hzoi_chairman	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2016-11-15 21:34:13	内存使用	1.84 MiB

#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
int read()
{
	int x,f=1;
	char ch;
	while(ch=getchar(),!isdigit(ch))if(ch=='-')f=-1;
	x=ch-48;
	while(ch=getchar(),isdigit(ch))x=x*10+ch-48;
	return x*f;
}
#define maxn 60
int f[110][maxn][maxn],a[maxn][maxn];
int main()
{
	freopen("message.in","r",stdin);
	freopen("message.out","w",stdout);
	int n=read(),m=read();
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			a[i][j]=read();
	for(int k=1;k<=m+n-3;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
			{
				if(i==j||k<i-2||k<j-2)continue;//注意去掉不合法情况
				f[k][i][j]=max(f[k][i][j],f[k-1][i-1][j]);
				f[k][i][j]=max(f[k][i][j],f[k-1][i][j-1]);
				f[k][i][j]=max(f[k][i][j],f[k-1][i-1][j-1]);
				f[k][i][j]=max(f[k][i][j],f[k-1][i][j]);
				f[k][i][j]+=a[i][k-i+2]+a[j][k-j+2];
			}
	printf("%d",max(f[n+m-3][n][n-1],f[n+m-3][n-1][n]));//while(1);
//	system("pause");
	fclose(stdin);
	fclose(stdout);
}