记录编号	46985	评测结果	AAAAAAAAAA
题目名称	[NOIP 2008]传纸条	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2012-10-30 09:49:14	内存使用	4.81 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int map[60][60],f[120][60][60];

int maxint(int a,int b)
{
	if (a>b)
		return(a);
	return(b);
}

int main(void)
{
	freopen("message.in","r",stdin);
	freopen("message.out","w",stdout);
	int i,j,k,n,m,stepsum;
	cin>>n>>m;
	for (i=1;i<=n;i++)
		for (j=1;j<=m;j++)
			cin>>map[i][j];
	stepsum=n+m-2;
	for (i=1;i<=stepsum;i++)
	{
		//(1+i-j,1+j)
		//(1+i-k,1+k)
		for (j=0;j<=i;j++)
		{
			if (!(1+i-j>=1&&1+i-j<=n&&1+j>=1&&1+j<=m))
				continue;
			for (k=0;k<=i;k++)
			{
				if (!(1+i-k>=1&&1+i-k<=n&&1+k>=1&&1+k<=m))
					continue;
				if (j==k&&i!=stepsum)
					continue;
				f[i][j][k]=maxint(maxint(f[i-1][j][k],f[i-1][j][k-1]),maxint(f[i-1][j-1][k],f[i-1][j-1][k-1]));
				f[i][j][k]+=map[1+i-j][1+j]+map[1+i-k][1+k];
			}
		}
	}
	cout<<f[stepsum][m-1][m-1]<<endl;
	return(0);
}