2978:Colored stones

keyword

動的計画法　C++

概要

長さn(<100)の数列が与えられる。各要素は1からk(<=5)の自然数である。いくつかの要素を取り除いて全ての要素が連続する様にしたいとき(111332444など)、最小でいくつ取り除く必要があるか求める問題。
kが小さいのでビットDPが思い浮かぶ。dp[n][既に置かれている要素][直前の要素]で計算できる。計算量はO(n* 2^k * k)。

int main(){
    int n, m;
    int i, j, k;
    int ns[102];
    int dp[102][1<<5][5];

    while(n = readint(), m = readint(), n){
        REP(i,n) ns[i] = readint() - 1;
        REP(i,n+1)REP(j,1<<m)REP(k,m) dp[i][j][k] = 1<<10;

        REP(k,m)dp[0][0][k] = 0;
        REP(i,n){
            int col = ns[i];
            REP(j,1<<m)REP(k,m)if(dp[i][j][k] < (1<<10)){
                if(!j){
                    dp[i+1][1<<col][col] = min(dp[i+1][1<<col][col], dp[i][j][k]);
                    dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k] + 1);
                }
                else if(k == col){
                    dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k]);
                }
                else if(j & (1<<col)){
                    dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k] + 1);
                }
                else{
                    dp[i+1][j|(1<<col)][col] = min(dp[i+1][j|(1<<col)][col], dp[i][j][k]);
                    dp[i+1][j][k] = min(dp[i+1][j][k], dp[i][j][k] + 1);
                }
            }
        }


        int ans = 1<<10;
        REP(j,1<<m)REP(k,m) ans = min(ans, dp[n][j][k]);
        printf("%d\n",ans);
    }

    return 0;
}