记录编号	238454	评测结果	AAAAAAAAAA
题目名称	[NOIP 1999]拦截导弹	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2016-03-19 09:07:03	内存使用	0.30 MiB

#include<cstdio>
#include<cstring>
int h[1005];
int c[1005];//c[i]:拦截i枚导弹，所余留的最大高度。此数组在dp过程中动态更新  
int n=0,ans=0;
int bi_search(int x){
	int l=0,r=ans,mid;
	while(l<=r){
//		printf("(%d %d)",l,r);
		mid=(l+r)>>1;
		if(c[mid]>=x){
			l=mid+1;
		}else{
			r=mid-1;
		}
	}
	return l-1;
}
void dp1(){
	c[0]=1<<25;int tmp;
	for(int i=0;i<n;++i){
		tmp=bi_search(h[i])+1;
		if(h[i]>c[tmp])c[tmp]=h[i];
		if(tmp>ans)ans=tmp;
	}
}
int bi_search2(int x){
	int l=0,r=ans,mid;
	while(l<=r){
		mid=(l+r)>>1;
		if(c[mid]<=x)l=mid+1;
		else r=mid-1;
	}
	return l-1;
}
void dp2(){
	memset(c,127,sizeof(c));
	c[0]=0;
	ans=0;int tmp;
	for(int i=0;i<n;++i){
		tmp=bi_search2(h[i])+1;
		if(h[i]<c[tmp])c[tmp]=h[i];
		if(tmp>ans)ans=tmp;
	}
}
int main(){
	freopen("missile.in","r",stdin);
	freopen("missile.out","w",stdout);
	while(scanf("%d",h+n)!=EOF)n++;
	dp1();
	printf("%d\n",ans);
	dp2();
	printf("%d\n",ans);
	fclose(stdin);fclose(stdin);
	return 0;
}