Collecting T [第五回 アルゴリズム実技検定 L]

https://atcoder.jp/contests/past202012-open/tasks/past202012_l

前提知識

• 区間DP

解説

https://atcoder.jp/contests/past202012-open/submissions/22298486

区間DPで解くことができる。
なぜ区間DP感があるかというと、削除できる領域を考えてみると、どれも区間になっていることが分かる。
a???b??????cでabcと消すためには?が全部消えている必要があるためである。
区間[L,R]を考えるとL＜m＜Rを選択して、S[L]=T[0], S[m]=T[1], S[R]=T[2]であるものを探せばいい。
その間の部分は全部消えている必要があるので、区間の長さと消せた個数から全部消えているかを判定する。
区間DPであるということが思いつけば、そこからはそれほど難しくない。

int N; string S, T;
//---------------------------------------------------------------------------------------------------
bool vis[101][101];
int memo[101][101];
int solve(int l, int r) {
    if (l > r) return 0;
    if (vis[l][r]) return memo[l][r];
    vis[l][r] = true;

    rep(m, l, r) chmax(memo[l][r], solve(l, m) + solve(m + 1, r));

    if (S[l] == T[0] && S[r] == T[2]) {
        rep(m, l + 1, r) if (S[m] == T[1]) {
            if (m - l - 1 == solve(l + 1, m - 1) * 3 && r - m - 1 == solve(m + 1, r - 1) * 3) {
                chmax(memo[l][r], solve(l + 1, m - 1) + solve(m + 1, r - 1) + 1);
            }
        }
    }
    
    return memo[l][r];
}
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S >> T;
    cout << solve(0, N - 1) << endl;
}