SRM 400 Div1 Medium: ReversalChain

問題

0と1から成る文字列initをgoalに変換する。できる操作は区間(i, j)の反転(ビットの反転ではなく、文字列の反転)のみで、これをr(i, j)と書く。 が与えられた時に が成り立つとき、これをreversal chainと呼ぶ。initをgoalに変換する際の最小のreversal chainの長さ(操作の回数)を求めよ。

制約

解法

dp[len][i][j][k] := initのi番目の文字から始まる長さlenの部分文字列と、goalのj番目の文字から始まる長さlenの部分文字列を一致させるのに必要な最小の操作回数。k=0で偶数回反転、k=1で奇数回反転。

final int INF = Integer.MAX_VALUE/2;

public int minReversal(String init, String goal) {
    int n = init.length();

    int[][][][] dp = new int[n+1][n][n][2];

    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            for (int k=0; k<2; k++) {
                if (init.charAt(i) != goal.charAt(j))
                    dp[1][i][j][k] = INF;
            }
        }
    }

    for (int len=2; len<=n; len++) {
        for (int i=0; i<=n-len; i++) {
            for (int j=0; j<=n-len; j++) {
                for (int k=0; k<2; k++) {
                    int a = init.charAt(i) != goal.charAt(j) ? INF : dp[len-1][i+1][j+1][0] + k;
                    int b = init.charAt(i+len-1) != goal.charAt(j+len-1) ? INF : dp[len-1][i][j][0] + k;
                    int c = init.charAt(i) != goal.charAt(j+len-1) ? INF : dp[len-1][i+1][j][1] + (k+1)%2;
                    int d = init.charAt(i+len-1) != goal.charAt(j) ? INF : dp[len-1][i][j+1][1] + (k+1)%2;

                    dp[len][i][j][k] = Math.min(Math.min(a,b),Math.min(c,d));
                }
            }
        }
    }

    return dp[n][0][0][0] == INF ? -1 : dp[n][0][0][0];
}