はまやんはまやんはまやん

hamayanhamayan's blog

Candies [AtCoder Regular Contest 090 C]

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;
}