记录编号	256442	评测结果	AAAAAAAAAA
题目名称	[NOIP 2008]传纸条	最终得分	100
用户昵称	Janis	是否通过	通过
代码语言	C++	运行时间	0.034 s
提交时间	2016-04-30 13:11:08	内存使用	33.27 MiB

//状态：dp[p][x1][x2]表示走到当前位置，好感度和的最大值 
//转移方程：dp[p][x1][x2]=max{dp[p-1][x1-1][x2],dp[p-1][x1][x2-1],dp[p-1][x1][x2],dp[p-1][x1-1][x2-1]}+map[x1][p+1-x1]+map[x2][p+1-x2]; 
//边界：dp[m+n-2][m-1][m]为所求 

#include<cstdio>
#include<iostream>
#include<algorithm>

using namespace std;

const int maxn=50+3;
int m,n;
int map[maxn][maxn],dp[maxn*maxn][maxn][maxn];
void init(){
	for(int i=1;i<=m;i++)
		for(int j=1;j<=n;j++)cin>>map[i][j];
}
void work(){
	for(int p=2;p<=m+n-2;p++){
		for(int x1=1;x1<=p;x1++){
			for(int x2=1;x2<=x1-1;x2++){
				if(x1==x2)continue;//不能在同一位置 
				dp[p][x1][x2]=max(max(dp[p-1][x1-1][x2],dp[p-1][x1][x2-1]),max(dp[p-1][x1][x2],dp[p-1][x1-1][x2-1]))+map[x1][p+1-x1]+map[x2][p+1-x2];				
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	freopen("message.in","r",stdin);
	freopen("message.out","w",stdout);	
	cin>>m>>n;
	init();
	work();
	cout<<dp[m+n-2][m][m-1];
}