2385:Apple Catching

keyword

動的計画法　C++

概要

T(<1000)個の0 or 1な列が与えられる。0をとるか1の一方だけを得ることができる。最初は0を得る状態からスタートするが、W(<30)回までそれを変更することができる。最も多く得られる個数はいくつか求める問題。
dp[n番目まで処理した][変更の回数]としてDP。デバッグをはし先生に協力してもらった。

int main(){
    int w, t, i, j;
    t = readint();
    w = readint();

    REP(i,t) ts[i] = readint()-1;

    REP(i,t+1)REP(j,w+1) dp[i][j] = 0;

    REP(i,t){
        REP(j,w){
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+(ts[i]==((j+1)&1)));
            dp[i+1][j] = max(dp[i+1][j], dp[i][j]+(ts[i]==(j&1)));
        }
        dp[i+1][w] = max(dp[i+1][w], dp[i][w] + (ts[i]==(w&1)));
    }

    int ans = 0;
    REP(i,w+1){
        ans = max(ans, dp[t][i]);
    }

    printf("%d\n",ans);
    return 0;
}