记录编号	242806	评测结果	AAAAAAAAAA
题目名称	109.[NOIP 2004]合唱队形	最终得分	100
用户昵称	Hzoi_Yniverse	是否通过	通过
代码语言	C++	运行时间	0.004 s
提交时间	2016-03-28 15:23:59	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,a[110],b[110],f[110];
int Find1(int,int,int);
int Find2(int,int,int);
int main(){
	freopen("chorus.in","r",stdin);
	freopen("chorus.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	int Max=0;
	for(int t=0;t<=n;t++){
		int max1=0,max2=0;
		memset(b,0x7f,sizeof(b));memset(f,0,sizeof(f));b[0]=0;
		for(int i=1;i<=t;i++){
			if(t==0) break;
			int x=Find1(1,i,a[i]);
			b[x]=a[i];
			f[i]=x;
			if(max1<f[i]) max1=f[i];
		}
		memset(b,0,sizeof(b));memset(f,0,sizeof(f));b[0]=0x7f7f7f7f;
		for(int i=t+1;i<=n;i++){
			int x=Find2(1,i,a[i]);
			b[x]=a[i];
			f[i]=x;
			if(max2<f[i]) max2=f[i];
		}
		if(Max<max1+max2) Max=max1+max2;
	}
	printf("%d",n-Max);
	return 0;
}
int Find1(int l,int r,int h){
	while(l<=r){
		int mid=(l+r)>>1;
		if(b[mid]<h) l=mid+1;
		if(b[mid]==h) return mid;
		if(b[mid]>h) r=mid-1;
	}
	return l;
}
int Find2(int l,int r,int h){
	while(l<=r){
		int mid=(l+r)>>1;
		if(b[mid]<h) r=mid-1;
		if(b[mid]==h) return mid;
		if(b[mid]>h) l=mid+1;
	}
	return l;
}