問題概要

長さ $N$ の文字列 $S$ に対して、次の操作を好きな回数だけ行える。操作後の文字列の長さとして考えられる最小値を求めよ。

$S$ が連続する部分文字列として "of" を含むとき、それとその後に続く $K$ 文字以下の文字を削除する。

制約

$0 \le K \lt N \le 300$

考えたこと

入れ子構造的な感じなので、区間 DP が第一感だった。まずは次のような DP を立てた。

dp[l][r] ← 文字列 $S$ の区間 $\lbrack l, r)$ に対して最適に操作した場合に残る文字列の長さの最小値

そして、次の場合を処理した。

区間 $\lbrack l, r)$ を 2 つの区間 $\lbrack l, m)$ 、 $\lbrack m, r)$ とに分けて、それぞれできるだけ短くする
区間 $\lbrack l, r)$ の先頭の文字が 'o' であって、"o(.....)f...... " という形をしていて、(......) の部分は完全に消去できる場合

1 は簡単。2 については、(......) の部分を完全に消去できるかどうかは dp 値を見ればわかる。しかし、最初は

o......f...(.....)...

のようなパターンで、後ろの (.....) の中身が消せる場合を失念してしまった。これに対処するために、僕は DP の定義を次のように修正して考えた。

dp[l][r] ← 文字列 $S$ の区間 $\lbrack l, r)$ に対して最適に操作した場合に完全消去できない場合は、区間の長さの最小値。完全消去できる場合は、その上でさらに追加で後ろの文字をいくつか消去できる可能性がある場合は、その個数の最大値を -1 倍した値

このように修正することで、DP を組めた。計算量は $O(N^{3})$ となる。

コード

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

int main() {
    string S;
    int K;
    cin >> S >> K;
    
    int N = S.size();
    vector<vector<int>> dp(N+1, vector<int>(N+1, N));
    for (int i = 0; i < N; ++i) {
        dp[i][i] = 0;
        dp[i][i+1] = 1;
    }
    
    for (int between = 2; between <= N; ++between) {
        for (int l = 0; l + between <= N; ++l) {
            int r = l + between;
            
            for (int m = l+1; m < r; ++m) {
                if (dp[l][m] > 0) {
                    chmin(dp[l][r], dp[l][m] + max(dp[m][r], 0));
                } else {
                    chmin(dp[l][r], dp[l][m] + dp[m][r]);
                }
            }
            if (S[l] == 'o') {
                for (int m = l+1; m < r; ++m) {
                    if (dp[l+1][m] <= 0 && S[m] == 'f') {
                        int rem = r - (m+1);
                        chmin(dp[l][r], rem - K);
                    }
                }
            }
        }
    }
    cout << max(dp[0][N], 0) << endl;
}

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

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

AtCoder ABC 325 G - offence (黄色, 575 点)

問題概要

制約

考えたこと

コード