範例程式碼 uva1366
//uva1366
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, m, i, j;
vector<vector<int>> y(500, vector<int>(500));
vector<vector<int>> b(500, vector<int>(500));
vector<vector<int>> y2(500, vector<int>(500));
vector<vector<int>> b2(500, vector<int>(500));
vector<vector<int>> dp(500, vector<int>(500));
scanf("%d%d", &n, &m);
while (n != 0 || m != 0) {
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j)
scanf("%d", &y[i][j]);
}
for (i = 0; i < n; ++i) {
for (j = 0; j < m; ++j)
scanf("%d", &b[i][j]);
}
for (i = n - 1; i >= 0; --i) {
y2[i][m - 1] = y[i][m - 1];
for (j = m - 2; j >= 0; --j)
y2[i][j] = y2[i][j + 1] + y[i][j];
}
for (i = n - 2; i >= 0; --i) {
for (j = m - 1; j >= 0; --j)
y2[i][j] += y2[i + 1][j];
}
for (i = n - 1; i >= 0; --i) {
b2[i][m - 1] = b[i][m - 1];
for (j = m - 2; j >= 0; --j)
b2[i][j] = b2[i][j + 1] + b[i][j];
}
for (i = n - 2; i >= 0; --i) {
for (j = m - 1; j >= 0; --j)
b2[i][j] += b2[i + 1][j];
}
dp[n - 1][m - 1] = max(y[n - 1][m - 1], b[n - 1][m - 1]);
for (j = m - 2; j >= 0; --j)
dp[n - 1][j] = max(b2[n - 1][j], y[n - 1][j] + dp[n - 1][j + 1]);
for (i = n - 2; i >= 0; --i)
dp[i][m - 1] = max(y2[i][m - 1], b[i][m - 1] + dp[i + 1][m - 1]);
for (i = n - 2; i >= 0; --i) {
for (j = m - 2; j >= 0; --j)
dp[i][j] = max(b2[i][j] - b2[i + 1][j] + dp[i + 1][j], y2[i][j] - y2[i][j + 1] + dp[i][j + 1]);
}
printf("%d\n", dp[0][0]);
scanf("%d%d", &n, &m);
}
return 0;
}