记录编号	247860	评测结果	AAAAAAAAAA
题目名称	[NOIP 1999]拦截导弹	最终得分	100
用户昵称	水墨青花	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2016-04-09 20:17:30	内存使用	0.30 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<string>
 
using namespace std;

int BS(int,int,int);
void Work();

int a[1010];
int h[1010];
int f[1010];
int b[1010];

int ans1=0,ans2=0;


int main()
{
	freopen("missile.in","r",stdin);
	freopen("missile.out","w",stdout);
	
	memset(a,0,sizeof(a));
	memset(f,0,sizeof(f));
	memset(h,0,sizeof(h));
	memset(b,0,sizeof(b));
	
	Work();
	
	fclose(stdin);
	fclose(stdout);
	return 0;
}

void Work()
{
	int i=1;
	while(scanf("%d",&a[i])!=EOF)
	{
		int id=0;
		id=BS(1,ans1,a[i]);
		f[i]=id;
		
		if(f[i]>ans1)
		{
			ans1=f[i];
		}
		
		int x=0;
		for(int j=1;j<=ans2;j++)
		{
			if(h[j]>a[i])
			{
				x=j;
				break;
			}
		}
		if(x==0)
		{
			ans2++;
			x=ans2;
		}
		h[x]=a[i];
		
		i++;
	}
	printf("%d\n%d",ans1,ans2);
}

int BS(int l,int r,int num)
{
	while(l<=r)
	{
		int mid=0;
		mid=(l+r)>>1;
		
		if(num<=b[mid])
		{
			l=mid+1;
		}
		else
		{
			r=mid-1;
		}
	}
	b[l]=num;
	return l;
}