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