問題
http://tenka1-2016-qualb.contest.atcoder.jp/tasks/tenka1_2016_qualB_b
'('と')'から成る文字列Sがある。
カーソルは文字列の先頭から始まる。
以下の3つの処理が行えるとき、文字列Sを括弧の対応が取れた状態にする最小手数を答えよ。
1. カーソルを右に動かす
2. カーソルを左に動かす
3. カーソルが指す文字を'('なら')'、')'なら'('にする
2 <= |S| <= 100
| S | は偶数 |
帰納的考察（解説見た）
以下、N = |S|
1. 括弧の対応問題だし cnt[i] は使うんだろうなという感じ
cnt[i] = i文字目までの 「(」の数 - 「)」の数
2. 対応関係が正しいというのは、全てのcnt[i]が0以上でcnt[N-1]==0
3. 頭からこうなるように貪欲にやればいい？
4. だめだった
5. うーんうーん
――壁――
6. 基本を忘れていた
7. 「愚直解を考える」「全部の状態数を考える」
8. 行う処理の中でカーソルを左に動かすのは無駄
9. なので、各文字を変えるかどうかだけ考えればよいので、これで2^n通り
10. これだと多いので、指数オーダを多項式オーダに変えるアレを考える
11. DP!!!!!
dp[i][j][k] = i文字目までで最後に変更したのがj文字目でcntの数がkである最小の変更回数 dp[0][0][0] = 0, 他 = INF 更新式は長いのでソース参照 そんなに難しくないですけど、0 < kという条件をつけているのは、対応関係が正しい条件の1つに全てのcntが0以上というのがあるからです
実装
http://tenka1-2016-qualb.contest.atcoder.jp/submissions/858862
#define INF INT_MAX/2 string S; //----------------------------------------------------------------- int dp[101][101][101]; int solve() { int N = S.length(); rep(i, 0, N + 1) rep(j, 0, N + 1) rep(k, 0, N + 1) dp[i][j][k] = INF; dp[0][0][0] = 0; rep(i, 0, N) rep(j, 0, N) rep(k, 0, N + 1) if(dp[i][j][k] != INF){ if (S[i] == '(') { dp[i + 1][j][k + 1] = min(dp[i + 1][j][k + 1], dp[i][j][k]); if(0 < k) dp[i + 1][i][k - 1] = min(dp[i + 1][i][k - 1], dp[i][j][k] + 1); } else{ dp[i + 1][i][k + 1] = min(dp[i + 1][i][k + 1], dp[i][j][k] + 1); if (0 < k) dp[i + 1][j][k - 1] = min(dp[i + 1][j][k - 1], dp[i][j][k]); } } int ans = INF; rep(j, 0, N) ans = min(ans, dp[N][j][0] + j); return ans; } //----------------------------------------------------------------- int main() { cin >> S; cout << solve() << endl; }
