记录编号	149219	评测结果	AAAAAAAAAA
题目名称	[NOIP 1999]拦截导弹	最终得分	100
用户昵称	北城以北	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2015-02-21 00:30:41	内存使用	0.77 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
using namespace std;
int i,m,n,j,a[50000],xt[10000],hminxt[10000],t,f[50000]={1};
int main()
{
  freopen("missile.in","r",stdin);
  freopen("missile.out","w",stdout);
  n=1;
  while (cin>>a[n])
  {
	if (n==1)
	{
	  m=1;
	  xt[1]+=1;
	  hminxt[1]=a[n];
    }
    else
    {
	  t=10000000;
	  for (i=1;i<=m;++i)
	   if (hminxt[i]>a[n]&&hminxt[i]<t)
       {
		 t=hminxt[i];
		 j=i;
       }
	  if (t==10000000)
      {
	   m+=1;
	   xt[m]=1;
	   hminxt[m]=a[n];
      }
      else
      {
	   xt[j]+=1;
	   hminxt[j]=a[n];
      }
    }
    n+=1;
  }
 t=1;
 for(i=2;i<=n;++i)
  for (j=1;j<=i-1;++j)
   if (a[i]<a[j]&&f[j]+1>f[i])
	f[i]=f[j]+1;
 for (i=2;i<=n;++i)
  if (f[i]>t) t=f[i];
 cout<<t<<endl<<m;
 fclose(stdin);
 fclose(stdout);
 return 0;
}