[白俊3114]りんごとバナナ

質問:3114りんごとバナナ
タイプ:DP
の意見を打診計算を容易にするために、アップルは事前に行方向合または列方向合を求めた.

左に移動する場合:(r,c)->(r,c++1)に貴移動する場合から右座標が固定されているので(1,c++1,r-1,c++1)までの樹木は伐採されないことが確定するのでbana sum(1,c++1~r-1,c++1)を加えることができる.

上へ移動する場合:(r,c)->(r+1,c)に貴移動する場合から、上記(r+1,1~r+1,c-1)のように下向き座標が固定されている樹木は伐採されない.したがってapple sum(r+1,1~r+1,c-1)を加える.

左上移動:耳が(r,c)->(r+1,c+1)に移動した場合にbanan sum(1,c+1,c+1),apple sum(r+1,1~r+1,c)を加える.

解答:dp表は(i,j)の時にリンゴ+バナナの最大値に設定して、点火式は

dp[i][j] = max(
	dp[i+1][j] + apple[i+1][j-1],
    	dp[i][j+1]+banana[i-1][j+1],
    	dp[i+1][j+1] + apple[i+1][j] + banana[i][j+1])

コード#コード#

#include <bits/stdc++.h>

const int dx[4] = { 1,0,-1,0 };
const int dy[4] = { 0,-1,0,1 };

using namespace std;

int R, C, apple[1502][1502], banana[1502][1502];
int dp[1502][1502];

int dfs(int r, int c) {
	if (r == R && c == C) return 0;

	int& ret = dp[r][c];
	if (ret != -1) return ret;

	if(r + 1 <= R)
		ret = max(ret, dfs(r + 1, c) + apple[r + 1][c - 1]);
	if (c + 1 <= C)
		ret = max(ret, dfs(r, c + 1) + banana[r - 1][c + 1]);
	if (r + 1 <= R && c + 1 <= C)
		ret = max(ret, dfs(r + 1, c + 1) + apple[r + 1][c] + banana[r][c + 1]);

	return ret;
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> R >> C;
	for (int i = 1; i <= R; i++) {
		for (int j = 1; j <= C; j++) {
			string x;
			cin >> x;
			int b = 0, a = 0;
			x[0] == 'B' ? b = stoi(x.substr(1, -1)) : a = stoi(x.substr(1, -1));
			apple[i][j] = apple[i][j - 1] + a;
			banana[i][j] = banana[i - 1][j] + b;
		}
	}

	memset(dp, -1, sizeof(dp));
	cout << dfs(1, 1);

	return 0;
}