第2回 アルゴリズム実技検定 (PAST 002)

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    string S;
    cin >> N >> S;

    S = "_" + S;

    vll C(N + 1), D(N + 1);
    rep(i, N) cin >> C[i + 1];
    rep(i, N) cin >> D[i + 1];

    // dp[i][j]: i 文字目まで見たときの、対応が取れていない左カッコの数が j のときの最小コスト
    vvll dp(N + 1, vll(N + 1, INF));
    dp[0][0] = 0;
    rep2(i, 1, N + 1) {
        rep(j, N) {
            if (S[i] == '(') {
                chmin(dp[i][j + 1], dp[i - 1][j]);

                // 反転
                if (j - 1 >= 0)
                    chmin(dp[i][j - 1], dp[i - 1][j] + C[i]);
            } else {
                if (j - 1 >= 0)
                    chmin(dp[i][j - 1], dp[i - 1][j]);

                // 反転
                chmin(dp[i][j + 1], dp[i - 1][j] + C[i]);
            }

            // i 番目の要素を削除
            chmin(dp[i][j], dp[i - 1][j] + D[i]);
        }
    }
    cout << dp[N][0] << endl;
}