Lee • 2个月前
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;
}
评论:
请先登录,才能进行评论