#include<bits/stdc++.h>
using namespace std;
int a[30005],f[30005][2],n;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    if (a[1] == 1)
        f[1][2] = 1;
    else
        f[1][1] = 1;
    for (int i = 2; i <= n; i++) 
    {
        if (a[i] == 1) 
        {
            f[i][1] = f[i - 1][1];
            f[i][2] = min(f[i - 1][2], f[i - 1][1]) + 1;
        } 
        else 
        {
            f[i][1] = f[i - 1][1] + 1;
            f[i][2] = min(f[i - 1][2], f[i - 1][1]);
        }
    }
    cout << min(f[n][1], f[n][2]);
    return 0;
}

可以用f[i][j]表示只考虑前i个人，其中第i个人的批次为j的答案。

状态转移时需要分别讨论a[i]=1和a[i]=2的情况。

初始状态为只考虑1个人的情况，即f[1][j]。最终答案为f[n][1]和f[n][2]的最小值。

if (a[1] == 1)
	f[1][2] = 1;
else
	f[1][1] = 1;
for (int i = 2; i <= n; i++) {
	if (a[i] == 1) {
		f[i][1] = f[i - 1][1];
		f[i][2] = min(f[i - 1][2], f[i - 1][1]) + 1;
	} else {
		f[i][1] = f[i - 1][1] + 1;
		f[i][2] = min(f[i - 1][2], f[i - 1][1]);
	}
}
cout << min(f[n][1], f[n][2]);