【ABC175】E - Picking Goods

atcoder.jp

水diff後半にしては簡単？ D問題になってたらdiffが下がりそう。

解法

次のようなDPを考えます。
dp[i][j][k] ← (i, j)にいる時、既にi行でk個のアイテムを拾った場合の最大値

また、二次元配列Gを次のように定義します。
G[i][j] ← (i, j)に落ちているアイテムの価値、アイテムがなければ0

遷移は(i+1, j)と(i, j+1)で分けて考えます。
今回は配るDPで考えることにします。

(i+1, j)へ進む場合

行が変わるので、k=0にしか遷移しません。

k < 3のとき:　dp[i+1][j][0] ← max(dp[i+1][j][k], dp[i][j][k] + G[i][j])
k ≦ 3のとき:　dp[i+1][j][0] ← max(dp[i+1][j][k], dp[i][j][k])

上がアイテムを拾うとき、下が拾わないときを表しています。

(i, j+1)へ進む場合

行が変わらないので、アイテムを拾う場合はkをインクリメントして遷移します。

k < 3のとき:　dp[i][j+1][k+1] ← max(dp[i][j+1][k+1], dp[i][j][k] + G[i][j])
k ≦ 3のとき:　dp[i][j+1][k] ← max(dp[i][j+1][k], dp[i][j][k])

右上まで遷移できたら答えが分かります。

実装

void solve(long long R, long long C, long long K, std::vector<long long> r, std::vector<long long> c, std::vector<long long> v){
    vector<vector<long long>> G(R, vector<long long>(C, 0));
    REP (i, K) G[r[i]-1][c[i]-1] = v[i];

    vector<vector<vector<long long>>> dp(R+1, vector<vector<long long>>(C+1, vector<long long>(4, 0)));
    REP (i, R) {
        REP (j, C) {
            REP (k, 4) {
                if (G[i][j] != 0 && k != 3) {
                    // アイテムを拾って上に行く
                    chmax(dp[i + 1][j][0], dp[i][j][k] + G[i][j]); 
                    // アイテムを拾って右に行く
                    chmax(dp[i][j + 1][k + 1], dp[i][j][k] + G[i][j]); 
                }

                chmax(dp[i + 1][j][0], dp[i][j][k]); // アイテムを拾わず上に行く
                chmax(dp[i][j + 1][k], dp[i][j][k]); // アイテムを拾わず右に行く
            }
        }
    }

    long long ans = 0;
    REP (i, 4) {
        chmax(ans, dp[R][C-1][i]);
    }

    cout << ans << endl;
}