https://beta.atcoder.jp/contests/arc090/tasks/arc090_a
前提知識
解法
https://beta.atcoder.jp/contests/arc090/submissions/2026787
DPを使って解く。
dp[y][x] := 左上のマスから(x,y)のマスへ移動して得られるアメの最大値
dp[y][x] は dp[y-1][x]かdp[y][x-1]から遷移してくるので、最大値を取ってきて更新してくればいい。
int N, A[2][101], dp[2][101]; //--------------------------------------------------------------------------------------------------- void _main() { cin >> N; rep(y, 0, 2) rep(x, 0, N) cin >> A[y][x]; dp[0][0] = A[0][0]; rep(y, 0, 2) rep(x, 0, N) { if (x) chmax(dp[y][x], dp[y][x - 1] + A[y][x]); if (y) chmax(dp[y][x], dp[y - 1][x] + A[y][x]); } cout << dp[1][N - 1] << endl; }