[AtCoder] ABC 175 E – Picking Goods

2020年9月2日2020年12月13日

問題

方針

マス \( (i, j)\) にあるアイテムの価値を \( g(i, j) \) とします。アイテムがない場合は \( 0 \) とします。次に、マス \( (i, j)\) において \( i \) 行目のアイテムを \( k \) 個取った時のアイテムの価値の合計の最大値を \( a(i, j, k) \) とします。この配列を動的計画法によって更新します。

マス \( (i, j)\) から マス \( (i + 1, j) \) に移動するとき

このとき、マス \( (i + 1, j) \) のアイテムを拾うか拾わないかの選択があるので、アイテムを拾わないとき、

\[ a(i + 1, j, 0) = \max(a(i + 1, j, 0), \ a(i, j, k)) \ (0 \leq k \leq 3)\]

となり、アイテムを拾うとき、

\[ a(i + 1, j, 1) = \max(a(i + 1, j, 1), \ a(i, j, k) + g(i + 1, j)) \ (0 \leq k \leq 3)\]

と更新されます。

マス \( (i, j)\) から マス \( (i , j + 1) \) に移動するとき

上記と同様に、マス \( (i + 1, j) \) のアイテムを拾わないとき、

\[ a(i, j + 1, k) = \max(a(i, j + 1, 0), \ a(i, j, k)) \ (0 \leq k \leq 3)\]

アイテムを拾うとき、アイテムを \( 3 \) 個持っている状態からは遷移できないことに注意して、

\[ a(i, j + 1, k + 1) = \max(a(i, j + 1, 0), \ a(i, j, k) + g(i, j + 1)) \ (0 \leq k \leq 2)\]

となります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll g[3002][3002]{};
ll a[3002][3002][4]{};


int main() {
    int R, C, K;
    cin >> R >> C >> K;
    int r, c, v;
    for (int i = 0; i < K; i++) {
        cin >> r >> c >> v;
        g[r][c] = v;
    }

    for (int i = 0; i <= R; i++) {
        for (int j = 0; j <= C; j++) {
            for (int k = 0; k <= 3; k++) {
                a[i + 1][j][0] = max(a[i + 1][j][0], a[i][j][k]);
                a[i][j + 1][k] = max(a[i][j + 1][k], a[i][j][k]);
                a[i + 1][j][1] = max(a[i + 1][j][1], a[i][j][k] + g[i + 1][j]);
                if (k != 3) {
                    a[i][j + 1][k + 1] = max(a[i][j + 1][k + 1], a[i][j][k] + g[i][j + 1]);
                }
            }
        }
    }
    ll best = 0;
    for (int i = 0; i <= 3; i++) {
        best = max(best, a[R][C][i]);
    }
    cout << best << "\n";
    return 0;
}