80分求调,#6,#8
查看原帖
80分求调,#6,#8
1258100
wanttoac楼主2024/4/14 12:16
#include<bits/stdc++.h>
using namespace std;
int g[555][555];
int dp[555][555][555];
int main() {
	int n, m;
	cin >> n >> m;
	for (int i = 1; i <= n; i++)for (int j = 1; j <= m; j++)cin >> g[i][j];
	dp[1][1][1] = g[1][1];
	for (int i = 2; i <= 2*n-1; i++) {
		for (int j = 1; j <= i; j++) {
			for (int k = 1; k < j; k++) {
				dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k - 1]);
				dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j - 1][k ]);
				dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k - 1]);
				dp[i][j][k] = max(dp[i][j][k], dp[i - 1][j][k]);
				dp[i][j][k] += g[i - j + 1][j] + g[i - k + 1][k];
			}
		}
	}
	cout << dp[2 * n-1][n][n-1]+g[n][n];
	return 0;
}
2024/4/14 12:16
加载中...