记录编号	79081	评测结果	AAAAAAAAAAA
题目名称	[USACO Feb08] 麻烦的聚餐	最终得分	100
用户昵称	digital-T	是否通过	通过
代码语言	C++	运行时间	0.007 s
提交时间	2013-11-05 06:55:23	内存使用	0.43 MiB

#include<fstream>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
ifstream fi("egroup.in");
ofstream fo("egroup.out");
int N,d[30003],Ans;
void NO_DOWN()
{
	int Nodown[30003];
	Nodown[0]=0;
	int last[4];
	last[1]=last[2]=last[3]=0;
	for(int i=1;i<=N;i++)
	{
		Nodown[i]=1;
		for(int j=1;j<=3&&j<=d[i];j++)
			Nodown[i]=max(Nodown[i],Nodown[last[j]]+1);
		last[d[i]]=i;
	}
	Ans=Nodown[1];
	for(int i=2;i<=N;i++)
		Ans=max(Ans,Nodown[i]);
}
void NO_UP()
{
	int Noup[300003];
	Noup[N+1]=0;
	int first[4];
	first[1]=first[2]=first[3]=N+1;
	for(int i=N;i>=1;i--)
	{
		Noup[i]=1;
		for(int j=1;j<=3&&j<=d[i];j++)
			Noup[i]=max(Noup[i],Noup[first[j]]+1);
		first[d[i]]=i;
	}
	for(int i=1;i<=N;i++)
		Ans=max(Ans,Noup[i]);
}
int main()
{
	fi>>N;
	for(int i=1;i<=N;i++)
		fi>>d[i];
	NO_DOWN();
	NO_UP();
	fo<<N-Ans<<endl;
	return 0;
}