3807812_re.cpp

北大大牛代码 1240道题的原代码 超级权威

#include<stdio.h>

int A[30001], N, dp[30001][3];

int min(int a, int b) 
{
	return a < b ? a : b;
}

int f() 
{
	int i;

    dp[0][0] = dp[0][1] = dp[0][2] = 1;
	dp[0][A[0] - 1] = 0;
    for(i = 1; i < N; i++) 
	{
        dp[i][0] = dp[i - 1][0] + (A[i] != 1);
        dp[i][1] = min(dp[i - 1][0], dp[i - 1][1]) + (A[i] != 2);
        dp[i][2] = min(min(dp[i - 1][0], dp[i - 1][1]), dp[i - 1][2]) + (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, ans;
    for (i = 0; i < N; i++) 
		scanf("%d", A[i]);
    ans = f();
    for(i = 0; i < N; i++)
		A[i] = 4 - A[i];
    ans = min(ans, f());
    printf("%d\n", ans);
    return 0;
}