记录编号	163943	评测结果	AAAAAAAAAA
题目名称	[NOIP 2008]传纸条	最终得分	100
用户昵称	啊吧啦吧啦吧	是否通过	通过
代码语言	C++	运行时间	0.020 s
提交时间	2015-05-27 11:00:09	内存使用	1.34 MiB

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <fstream>
#define cin fin
#define cout fout

using namespace std;

ifstream fin("message.in");
ofstream fout("message.out");
const int MAXN = 51;
int f[MAXN][MAXN], dp[MAXN + MAXN][MAXN][MAXN] = {0}, n, m;

int main()
{
	ios::sync_with_stdio(false);
	
	cin >> m >> n;
	for(int i = 1; i <= m; i ++)
		for(int j = 1; j <= n; j ++)
			cin >> f[i][j];
	memset(dp, 0, sizeof(dp));
//	memset(fang, 0, sizeof(fang));
	//cout << sizeof(dp) / 1024 / 1024 << endl;
	
	for(int st = 1; st <= n - 1 + m - 1; st ++)
	{
		int t = min(st, m + n - 1 - 1);
		for(int i = 1; i <= t; i ++)
		{
			int j = st - i + 1;
			for(int k = i + 1; k <= t; k ++)
			{
				int l = st - k + 1, la = st - 1;
				int& ans = dp[st][i][k];
				ans = max(ans, dp[la][i][k]);
				ans = max(ans, dp[la][i][k - 1]);
				ans = max(ans, dp[la][i - 1][k]);
				ans = max(ans, dp[la][i - 1][k - 1]);
				ans += (f[i][j]  + f[k][l]);
			}
		}
	}
	cout << dp[n - 1 + m - 1][m - 1][m] << endl;
//	system("pause");
	return 0;
}