记录编号	215798	评测结果	AAAAAAAAAA
题目名称	[NOIP 1999]拦截导弹	最终得分	100
用户昵称	dateri	是否通过	通过
代码语言	C++	运行时间	0.053 s
提交时间	2015-12-24 15:14:01	内存使用	0.31 MiB

#include<stdio.h>
#include<stdlib.h>
int cmp(const void *x,const void *y)
{
	return *(int *)x-*(int *)y;
} 
int main()
{
	int a[3010]={0},b[3010]={0},c[30001]={0},n=-1,num,ans=1,max=0,flag=0,count=0,i,j;
	freopen("missile.in","r",stdin);
	freopen("missile.out","w",stdout);
	while(scanf("%d",&a[++n])==1);
	for(i=n-1;i>=0;i--)
	{
		max=0;
		for(j=0;j<a[i];j++)
		  if(c[j]>max)
		    max=c[j];
		if(c[a[i]]<max+1)
		  c[a[i]]=max+1;
	}
	max=0;
	for(i=0;i<30001;i++)
	  if(c[i]>max)
	    max=c[i];
	printf("%d\n",max);
	b[count++]=a[0];
	for(i=1;i<n;i++)
	{
		qsort(b,count,sizeof(b[0]),cmp);
		for(j=0;j<count;j++)
		  if(b[j]>=a[i])
		    {
		    	b[j]=a[i];
		    	break;
			}
		if(j==count)
		  {
		  	b[count++]=a[i];
		    ans++;
		  }
	}
	printf("%d",ans);
	return 0;
}