String Merging [CodeChef January Challenge 2018 D]

https://www.codechef.com/JAN18/problems/STRMRG

N要素の文字列A、M要素の文字列Bがある。
これをマージして文字列Cを作る。
マージルール

• AとBから全ての文字を使う
• Aの文字列の順番、Bの文字列の順番は崩さすマージする

　
関数Fを用意する
F(S) := 文字列Sの中で文字が同じ隣接する文字を1つと考えた時のグループ数
F("aaabbbaa") = 3 （aのグループ,bのグループ,aのグループで3つ）
F("abcabc") = 6
F("aabbccab") = 5
　
作れる文字列Cの中でのF(C)の最小値は？

解法

DPで解く。
dp[a][b][c] := 文字列Aからa文字使って、文字列Bからb文字使って、最後がc(=0でA, =1でB)である文字列の関数Fの値
このDPを使うなと考えながら遷移を考えると解ける。
2文字列をマージするというのと、順番は崩さないということと制約からこのDPを思いついた。
遷移はコードを見てもらう方が分かりやすいと思うが、後ろに文字列Aか文字列Bから文字を追加する時に最後の文字と同じでないなら+1して遷移先のDPの値を更新していくように書く。

#define INF INT_MAX/2
int N, M; string A, B;
int dp[5050][5050][2];
//---------------------------------------------------------------------------------------------------
void solve() {
    cin >> N >> M >> A >> B;
    rep(a, 0, N + 1) rep(b, 0, M + 1) rep(c, 0, 2) dp[a][b][c] = INF;
    dp[1][0][0] = 1;
    dp[0][1][1] = 1;
    rep(a, 0, N + 1) rep(b, 0, M + 1) rep(c, 0, 2) if(dp[a][b][c] != INF) {
        int last;
        if (c == 0) last = A[a - 1] - 'a';
        else last = B[b - 1] - 'a';

        if (a < N) {
            int aa = A[a] - 'a';
            int cc = dp[a][b][c];
            if (aa != last) cc++;
            dp[a + 1][b][0] = min(dp[a + 1][b][0], cc);
        }

        if (b < M) {
            int bb = B[b] - 'a';
            int cc = dp[a][b][c];
            if (bb != last) cc++;
            dp[a][b + 1][1] = min(dp[a][b + 1][1], cc);
        }
    }

    int ans = min(dp[N][M][0], dp[N][M][1]);
    printf("%d\n", ans);
}
//---------------------------------------------------------------------------------------------------
void _main() {
    int T; cin >> T;
    rep(t, 0, T) solve();
}