wrong2

Lee  •  2个月前


include <bits/stdc++.h>

using namespace std; int dp[1001][1001]; int a[1001][1001]; int sum[1001][1001];

int main() {

int n, m;
cin >> n >> m;

for (int i = 1; i <= n; i++) {

	for (int j = 1; j <= m; j++) {

		cin >> a[i][j];
		sum[i][j] = sum[i - 1][j] + a[i][j];
	}
}

memset(dp, 0xf0, sizeof dp);
dp[1][1] = a[1][1];

for (int i = 2; i <= n; i++) {

	dp[i][1] = dp[i - 1][1] + a[i][1];
}

for (int j = 2; j <= m; j++) {

	for (int i = 1; i <= n; i++) {

		int ans = -1e9;

		for (int k = i + 1; k <= n; k++) {

			ans = max(ans, dp[k][j - 1] + sum[k][j] - sum[i][j]);
		}

		dp[i][j] = max(dp[i][j - 1], max(dp[i - 1][j], ans)) + a[i][j];
	}
}

for (int i = 1; i <= n; i++) {

	for (int j = 1; j <= m; j++) {

		cout << dp[i][j] << " ";
	}

	cout << endl;
}

return 0;

}


评论:

请先登录,才能进行评论