けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

鉄則本 A21 - Block Game (2Q, ★4)

区間の左端と右端を添字にもちつつ、左端を除去したり右端を除去したりする DP。鉄則本の問題なので、コードのみ。

問題概要

ブロック  1, 2, \dots, N がこの順に一列に並んでいて、「左端のブロックまたは右端のブロックを除去する」という操作を  N 回行ってブロックを無くす。

 i = 1, 2, \dots, N に対して、ブロック  i をブロック  P_{i} よりも先に除去すると、 A_{i} 点加算される。

最大スコアを求めよ。

制約

  •  1 \le N \le 2000

コード

ここでは、メモ化再帰で書いた。

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

int main() {
    int N;
    cin >> N;
    vector<int> P(N), A(N);
    for (int i = 0; i < N; i++) cin >> P[i] >> A[i], P[i]--;

    vector dp(N+1, vector(N+1, -1));
    auto rec = [&](auto rec, int l, int r) {
        if (r - l <= 1) return 0;
        if (dp[l][r] != -1) return dp[l][r];
        int res = 0;

        // 左を除く場合
        int add = 0;
        if (l+1 <= P[l] && P[l] < r) add = A[l];
        res = max(res, rec(rec, l+1, r) + add);

        // 右を除く場合
        add = 0;
        if (l <= P[r-1] && P[r-1] < r-1) add = A[r-1];
        res = max(res, rec(rec, l, r-1) + add);

        //cout << l << ", " << r << ": " << res << endl;
        return dp[l][r] = res;
    };
    cout << rec(rec, 0, N) << endl;
}