记录编号	161007	评测结果	AAAAAAAAAAA
题目名称	[USACO Feb08] 麻烦的聚餐	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.023 s
提交时间	2015-04-30 14:52:32	内存使用	1.00 MiB

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
using namespace std;
int a[30001],f[30001],c[30001],fa[30001],b[30001],d[30001];
int main()
{   freopen("egroup.in","r",stdin);
	freopen("egroup.out","w",stdout);
	int p,n;
    scanf("%d",&n);
	for(int i=1;i<=n;++i)
	{   scanf("%d",&p);
		a[i]=p;
		c[n+1-i]=p;
		f[i]=1;
		fa[i]=1;
	}
	memset(b,24,sizeof(b));
	b[0]=0;
	int tot=0,tott=0;
	for(int i=1;i<=n;++i)
	{   int t=i,s=0;
		while(1)
		{   if(s>t) break;
			int temp=(t+s)>>1;
			if(b[temp]<=a[i]) s=temp+1;
			else
			 t=temp-1;
		}
		f[i]=s;
		if(b[s]>=a[i]) b[s]=a[i];
		if(f[i]>tot) tot=f[i];
	}
	tot=n-tot;
	//cout<<tot<<endl;
	memset(d,24,sizeof(d));
	d[0]=0;
	for(int i=1;i<=n;++i)
	{
        int t=i,s=0;
		while(1)
		{   if(s>t) break;
			int temp=(t+s)>>1;
			if(d[temp]<=c[i]) s=temp+1;
			else
			 t=temp-1;
		}
		fa[i]=s;
		if(d[s]>=c[i])d[s]=c[i];
		if(fa[i]>tott) tott=fa[i];
	}
	tott=n-tott;
	printf("%d",min(tot,tott));
	//system("pause");
}