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

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

• 問題へのリンク

問題概要

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

に対して、ブロック をブロック よりも先に除去すると、 点加算される。

最大スコアを求めよ。

制約

• 

コード

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

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