题目

一个M*N矩阵中有不同的正整数，经过这个格子，就能获得相应价值的奖励，先从左上走到右下，再从右下走到左上。第1遍时只能向下和向右走，第2遍时只能向上和向左走。两次如果经过同一个格子，则该格子的奖励只计算一次，求能够获得的最大价值。

例如：3 * 3的方格。

1 3 3

2 1 3

2 2 1

能够获得的最大价值为：17。1 -> 3 -> 3 -> 3 -> 1 -> 2 -> 2 -> 2 -> 1。其中起点和终点的奖励只 计算1次。

Input

第1行：2个数M N，中间用空格分隔，为矩阵的大小。(2 <= M, N <= 200) 第2 - N + 1行：每行M个数，中间用空格隔开，对应格子中奖励的价值。(1 <= A[i,j] <= 10000)

Output

输出能够获得的最大价值。

Sample Input

3 3

1 3 3

2 1 3

2 2 1

Sample Output

17

代码

#include <bits/stdc++.h>
using namespace std;
const int ma = 205;
int n, m, dp[ma][ma][2 * ma], a[ma][ma];
long long ans;
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
    	for (int j = 1; j <= m; j++) {
    		cin >> a[i][j];
		}
	}
	int cnt = n + m;
    for (int k = 1; k <= cnt; k++) {
    	for (int i = 1; i <= n; i++) {
    		for (int j = 1; j <= n; j++) {
				int dp1 = max(dp[i][j][k - 1], dp[i - 1][j - 1][k - 1]);
				int dp2 = max(dp[i][j - 1][k - 1], dp[i - 1][j][k - 1]);
				if (i == j) {
					dp[i][j][k] = max(dp1, dp2) + a[i][k - i];
				} else {
					dp[i][j][k] = max(dp1, dp2) + a[i][k - i] + a[j][k - j];
				}
			}
		}
	}
    ans = dp[n][n][cnt];
    printf("%lld", ans);
    return 0;
}