比赛 清明时节雨纷纷,今天天气很晴朗 评测结果 AAAAAAAAAA
题目名称 传纸条 最终得分 100
用户昵称 sxysxy 运行时间 0.319 s
代码语言 C++ 内存使用 35.23 MiB
提交时间 2017-04-07 19:25:23
显示代码纯文本
#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN (55)
int map[MAXN][MAXN];
int dp[MAXN][MAXN][MAXN][MAXN];

int main()
{
	freopen("message.in", "r", stdin);
	freopen("message.out", "w", stdout);
	int i,j,k,l;
	int n,m;
	cin >> m >> n;
	for(i = 1; i <= m; i++)
		for(j = 1; j <= n; j++)
			scanf("%d", &map[i][j]);
	
	for(i = 1; i <= m; i++)
	{
		for(j = 1; j <= n; j++)
		{
			for(k = 1; k <= m; k++)
			{
				for(l = 1; l <= n; l++)
				{
					dp[i][j][k][l] = max(dp[i][j][k][l], dp[i-1][j][k-1][l]);
					dp[i][j][k][l] = max(dp[i][j][k][l], dp[i-1][j][k][l-1]);
					dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j-1][k-1][l]);
					dp[i][j][k][l] = max(dp[i][j][k][l], dp[i][j-1][k][l-1]);
					dp[i][j][k][l] += map[i][j];
					if(i != k || j != l)
						dp[i][j][k][l] += map[k][l];
				}
			}
		}
	}
	cout << dp[m][n][m][n];
	return 0;
}