记录编号	251770	评测结果	AAAAAAAAAA
题目名称	[NOIP 2008]传纸条	最终得分	100
用户昵称	洛克索耶夫	是否通过	通过
代码语言	C++	运行时间	0.015 s
提交时间	2016-04-18 16:57:44	内存使用	6.94 MiB

#include<cstdio>
#include<algorithm>
using namespace std;

int f[120][120][120];
int a[120][120];
//每个纸条都要走m+n-2步才能到达目标 
//f[k][i1][j1]表示两个纸条都走了k步,第一个纸条行坐标为i1,第2个纸条横坐标为i2最优值
//两纸条列坐标j1=k-i1+2,j2=k-i2+2 
//a[i][j]:位于[i][j]位置同学的好心值

int Max(int a, int b)
{
	return a>b?a:b;
}

int GetMax(const int& a, const int& b, const int& c, const int& d)
{
	int ret=0;
	ret=Max(a,ret);
	ret=Max(b,ret);
	ret=Max(c,ret);
	ret=Max(d,ret);
	return ret;
}

int main()
{
	freopen("message.in","r",stdin);
	freopen("message.out","w",stdout);
	int m,n,w1,w2,w3,w4;
	scanf("%d%d",&m,&n);
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)
			scanf("%d",&a[i][j]);
			
	for(int k=1;k<=m+n-2;k++){
		for(int i1=1;i1<=m;i1++){
			for(int i2=1;i2<=m;i2++){
				if(i1!=i2){
					w1=f[k-1][i1][i2];
					w2=f[k-1][i1-1][i2];
					w3=f[k-1][i1][i2-1];
					w4=f[k-1][i1-1][i2-1];
					f[k][i1][i2]=GetMax(w1,w2,w3,w4)+a[i1][k-i1+2]+a[i2][k-i2+2];
				}		
			}
		}
	}	
	
//	for(int i1=1;i1<=m;i1++){
//		for(int i2=1;i2<=m;i2++){
//			for(int k=1;k<=m+n+2;k++){
//				printf("%d  ",f[k][i1][i2]);
//			}
//		}
//	}
	//fclose(stdin);fclose(stdout);
	printf("%d\n",Max(f[m+n-2][m][m-1],f[m+n-2][m-1][m]));
	return 0;
}