はまやんはまやんはまやん

hamayanhamayan's blog

Parentheses [第二回 アルゴリズム実技検定 K]

https://atcoder.jp/contests/past202004-open/tasks/past202004_k

前提知識

解説

https://atcoder.jp/contests/past202004-open/submissions/12899146

どことなく問題が編集距離のDPに似ている。
類題を解いたことがあるので、以下のDPが思いつくが、0から思いつくのは厳しい所があるかもしれない。
それかかっこは「diff=(の個数-)の個数」で考えるのが、典型方針であるので、そこから思いついてもいいかもしれない。
dp[i][diff] := i文字目まで見終わっていて、これまでのかっこ列についてdiff=(の個数-)の個数である最小コスト
行える操作としては、そのままにしておくか(stay)、反転させるか(flip)、削除するか(erase)の3択なので、
計算自体はO(N2)で間に合う。

int N; string S; int C[3010], D[3010];
ll dp[3010][3010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S;
    rep(i, 0, N) cin >> C[i];
    rep(i, 0, N) cin >> D[i];

    rep(i, 0, N + 1) rep(diff, 0, N + 1) dp[i][diff] = infl;
    dp[0][0] = 0;

    rep(i, 0, N) rep(diff, 0, N) {
        int d = 0;
        if (S[i] == '(') d = 1;
        else d = -1;

        // stay
        if (0 <= diff + d) chmin(dp[i + 1][diff + d], dp[i][diff]);

        // flip
        if (0 <= diff - d) chmin(dp[i + 1][diff - d], dp[i][diff] + C[i]);

        // erase
        chmin(dp[i + 1][diff], dp[i][diff] + D[i]);
    }

    cout << dp[N][0] << endl;
}