最初、同じ行の「連続する 3 個」しか選べないのだと誤読してしまった...

問題概要

二次元座標平面上で、(1, 1) から (R, C) へと格子点を辿って最短経路で進みたい (上か右にしか行けない)。

K 個の座標 ( $x_{i}, y_{i}$ ) に価値 $v_{i}$ のアイテムがある。通った経路中のアイテムを拾うことができる。

アイテムのある格子点上を通過しても、アイテムを拾わないという選択も可能である
同じ y 座標 (行) のアイテムは最高で 3 個までしか拾うことができない

上手に経路と拾うアイテムを選ぶことで、拾うアイテムの価値の最大値を求めよ。

制約

$1 \le R, C \le 3000$
$1 \le K \le \min(2 \times 10^{5}, R \times C)$

考えたこと

とりあえず、 $R, C$ が小さいので、二次元配列に全部確保しても大丈夫だし、二次元配列全体を舐めるようなことをしても計算時間大丈夫！！！

さて、「同じ行のアイテムは 3 個までしか拾うことができない」という制約がなければ、割とかなり典型問題になる。その場合は、

dp[ i ][ j ] ← マス (i, j) まで来たときの回収したアイテムの価値の総和の最大値

と定義してあげて、マス ( i, j ) にあるアイテムの価値を v[ i ][ j ] (存在しなければ 0) として、

chmax(dp[ i ][ j ] , dp[ i - 1 ][ j ] + v[ i ][ j ])
chmax(dp[ i ][ j ], dp[ i ][ j - 1 ] + v[ i ][ j ])

という感じで行ける。なお、ここでは集める DP で書いた。

同じ行のアイテムは 3 個まで

この制約が加わっても、DP をちょっと拡張してあげれば解ける！

dp[ i ][ j ][ k ] ← マス (i, j) まで来たとき、その時点で i 行目のアイテムは k 個回収した状態としたときの、回収したアイテムの価値の総和の最大値

こうしてあげることで、

上へ行く遷移

この場合は、回収アイテム個数がリセットされるので、回収する場合と回収しない場合とに分けて考えて、

chmax(dp[ i ][ j ][ 0 ], dp[ i - 1 ][ j ][ k ])
chmax(dp[ i ][ j ][ 1 ], dp[ i - 1 ][ j ][ k ] + v[ i ][ j ])

右へ行く遷移

この場合は、回収する場合としない場合とに分けてあげて

chmax(dp[ i ][ j ][ k ], dp[ i ][ j - 1 ][ k ])
chmax(dp[ i ][ j ][ k ], dp[ i ][ j - 1 ][ k - 1 ] + v[ i ][ j ])

以上の雰囲気で解ける！計算量は $O(RC)$ 。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

long long v[3100][3100], dp[3100][3100][5];
int main() {
    int R, C, K;
    cin >> R >> C >> K;
    memset(v, 0, sizeof(v));
    for (int i = 0; i < K; ++i) {
        long long r, c, t;
        cin >> r >> c >> t;
        v[r][c] = t;
    }
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i <= R; ++i) {
        for (int j = 0; j <= C; ++j) {
            for (int k = 0; k <= 3; ++k) {
                // 上へ行く
                if (i-1 >= 0) {
                    chmax(dp[i][j][0], dp[i-1][j][k]);
                    chmax(dp[i][j][1], dp[i-1][j][k] + v[i][j]);
                }
 
                // 右へ行く
                if (j-1 >= 0) {
                    chmax(dp[i][j][k], dp[i][j-1][k]);
                    if (k-1 >= 0)
                        chmax(dp[i][j][k], dp[i][j-1][k-1] + v[i][j]);
                }
            }
        }
    }
    long long res = 0;
    for (int k = 0; k <= 3; ++k) chmax(res, dp[R][C][k]);
    cout << res << endl;
}