範例程式碼 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;
}