题解 P2837 【晚餐队列安排】

深海鱼的眼泪 · 2017-04-28 20:35:28 · 题解

怎么感觉没几个题解是写DP的呢？难道这真的是道假DP？

如果用DP其实很好想啊，用dp[i][0]表示第i头奶牛为1时需改的最小数量，dp[i][1]表示第i头奶牛为2时需改的最小数量，

如果第i头奶牛原来为1，则dp[i][0]=dp[i-1][0],dp[i][1]=min(dp[i-1][1],dp[i-1][0])+1，然后原来为2的情况以此类推啦~

最后只要比较dp[n][0]和dp[n][1]就行了。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
int d[30010];
int dp[30005][2];
int main(){
    int n,i;
    cin>>n;
    for (i=1;i<=n;++i){
        cin>>d[i];
    }
    dp[1][2-d[1]]=1;
    dp[1][d[1]-1]=0;
    for (i=2;i<=n;++i){
        if (d[i]==1){
            dp[i][0]=dp[i-1][0];
            dp[i][1]=min(dp[i-1][1],dp[i-1][0])+1;
        }else{
            dp[i][0]=dp[i-1][0]+1;
            dp[i][1]=min(dp[i-1][1],dp[i-1][0]);
        }
    }
    if (dp[n][0]>dp[n][1]) printf("%d",dp[n][1]);
    else printf("%d",dp[n][0]);
    return 0;
}