Flood Fill [Codeforces Round #538 (Div. 2) D]

https://codeforces.com/contest/1114/problem/D

N要素の色の配列Cがある。
ある要素を指定する。
指定の要素から以下の操作を何回か行って全ての色を同じにせよ。
操作「指定の要素と連結している（同じ色でつながっている）領域をある色に変える」

1≦N, C[i]≦5000

前提知識

• 区間DP

解説

https://codeforces.com/contest/1114/submission/49710431

区間DPをする。
dp[L][R][isLR] := 区間[L,R]がisLRの色に同色で塗られているようにする最小回数
（isLR=0ならC[L]の色になっていて、isLR=1ならC[R]の色になっている）
このDPにはどの要素から始まったかという情報が抜けているが、連結になった後は別にどこであっても状況は変わらないので、保持しておく必要はない。
連結直後の色は必ず左右の端のどちらかの色になっているはずなので、色は左右のどちらであるかだけ保持する。

int N, C[5010];
int dp[5010][5010][2];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;
    rep(i, 0, N) cin >> C[i];

    rep(L, 0, N) rep(R, 0, N) rep(isLR, 0, 2) dp[L][R][isLR] = inf;
    rep(i, 0, N) rep(isLR, 0, 2) dp[i][i][isLR] = 0;

    rep(len, 1, N + 1) rep(L, 0, N - len + 1) rep(isLR, 0, 2) {
        int R = L + len - 1;
        int nowcolor;
        if (isLR == 0) nowcolor = C[L];
        else nowcolor = C[R];

        if (0 < L) chmin(dp[L - 1][R][0], dp[L][R][isLR] + (C[L - 1] != nowcolor));
        if (R + 1 < N) chmin(dp[L][R + 1][1], dp[L][R][isLR] + (C[R + 1] != nowcolor));
    }

    int ans = min(dp[0][N - 1][0], dp[0][N - 1][1]);
    cout << ans << endl;
}