4112396_wa.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 26 行

#include<cstdio>

int A[1000000],N,dp[1000000][3];
int min(int a,int b) {return a<b?a:b;}
int fans() {
    dp[0][0]=dp[0][1]=dp[0][2]=1;
    dp[0][A[0]-1]=0;
    for(int i=1;i<N;i++) {
        dp[i][0] = dp[i-1][0]+1-(A[i]==1);
        dp[i][1] = min(dp[i-1][0],dp[i-1][1])+1-(A[i]==2);
        dp[i][2] = min(min(dp[i-1][0],dp[i-1][1]),dp[i-1][2])+1-(A[i]==3);
    }
    return min(min(dp[N-1][0],dp[N-1][1]),dp[N-1][2]);
}

int main() {
    scanf("%d",&N);
    int i,v;
    for(i=0;i<N;i++) scanf("%d",A+i);
    v = fans();
    for(i=0;i<N;i++) A[i]=4-A[i];
    v <?= fans();
    printf("%d\n",v);
    return 0;
}