3670:Eating Together

keyword

動的計画法　C

概要

1,2,3が並んだ長さN(<30000)の列が与えられる。このとき、数字を書き換えることによって減少列か増加列にしたい。数字の書き換え回数を最小化する問題。
分かりやすいDP。減少と増加は別々に考える。dp[i項目][i-1項目の数値]とすれば全状態数は3*Nしかない。また状態遷移は1->2, 2->3だけでなく1->3があることにも注意。

nt solve(){
    int ret = 1<<29, i,j;
    for(i=0;i<N;i++)
        as[i]--;
    //check up
    for(i=0;i<=N;i++)
        for(j=0;j<3;j++)
            dp[i][j] = 1<<29;
    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    for(i=0;i<N;i++){
        for(j=0;j<3;j++){
            dp[i+1][j] = min(dp[i+1][j], dp[i][j] + (as[i]==j?0:1));
            if(j<2)
                dp[i+1][j+1] = min(dp[i+1][j+1], dp[i][j]+(as[i]==j+1?0:1));
            if(j<1)
                dp[i+1][j+2] = min(dp[i+1][j+2], dp[i][j]+(as[i]==j+2?0:1));
        }
    }
    ret = min(ret, dp[N][0]);
    ret = min(ret, dp[N][1]);
    ret = min(ret, dp[N][2]);

    //check down
    for(i=0;i<=N;i++)
        for(j=0;j<3;j++)
            dp[i][j] = 1<<29;
    dp[0][0] = dp[0][1] = dp[0][2] = 0;
    for(i=0;i<N;i++){
        for(j=0;j<3;j++){
            dp[i+1][j] = min(dp[i+1][j], dp[i][j] + (as[i]==j?0:1));
            if(j>0)
                dp[i+1][j-1] = min(dp[i+1][j-1], dp[i][j]+(as[i]==j-1?0:1));
            if(j>1)
                dp[i+1][j-2] = min(dp[i+1][j-2], dp[i][j]+(as[i]==j-2?0:1));
        }
    }
    ret = min(ret, dp[N][0]);
    ret = min(ret, dp[N][1]);
    ret = min(ret, dp[N][2]);

    return ret;
}