B - 天下一魔力発電 天下一プログラマーコンテスト2016予選B

問題概略
括弧の対応を取る時の最小操作回数
移動回数＋変更回数

制約<=100

解法
dpは状態の纏め上げだということを忘れていた。
愚直に考えると、2^100になってしまうが、現在見終わった場所、最後に変更した場所、(が開いている数が同じなら一つの状態に纏められる。
括弧が(か),変更する場合としない場合の4通りがある。操作回数を入れると処理が面倒なので、変更回数を入れることとする。

public static void solve() {
        //longを忘れるなオーバーフローするぞ
        char[] s = next().toCharArray();
        N = s.length;
        //ここまで見た。　最後の変更　開いた括弧の数。
        int[][][] dp = new int[N + 1][101][101];
        fill(dp, INF);
        dp[0][0][0] = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < i + 1; j++) {
                for (int k = 0; k < 101; k++) {
                    if (dp[i][j][k] == INF) continue;
                    //kは自分より左での個数
                    int now = dp[i][j][k];
                    if (s[i] == '(') {
                        dp[i + 1][j][k + 1] = Math.min(dp[i + 1][j][k + 1], now);
                        if (k > 0) dp[i + 1][i][k - 1] = Math.min(dp[i + 1][i][k - 1], now + 1);
                    } else {
                        //基本的に(にする
                        dp[i + 1][i][k + 1] = Math.min(dp[i + 1][i][k + 1], now + 1);
                        if (k > 0) dp[i + 1][j][k - 1] = Math.min(dp[i + 1][j][k - 1], now);
                    }
                }
            }
        }
        //i = N
        for (int j = 0; j < 101; j++) {
            chMin(dp[N][j][0] + j);
        }
        System.out.println(minRes);
    }