记录编号	43381	评测结果	AAAAA
题目名称	[NOIP 1999]拦截导弹	最终得分	100
用户昵称	Makazeu	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2012-10-10 08:41:57	内存使用	3.15 MiB

#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <cctype>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN=20;
string str; int N=0,Ans=0;
int Num[MAXN],F[MAXN]={0};
inline int Max(int a,int b){return a>b?a:b;}

int main()
{
	freopen("missile.in","r",stdin);
	freopen("missile.out","w",stdout);
	getline(cin,str); int now=0; str.push_back(' ');
	for(unsigned int i=0;i<str.size();i++)
	{
		if(!isdigit(str[i])) 
		{
			if(now==0) continue;
			Num[++N]=now;now=0;continue;
		}
		now=now*10+str[i]-'0';
	}
	//for(int i=1;i<=N;i++) cout<<Num[i]<<endl;
	for(int i=1;i<=N;i++)
	{
		F[i]=1;
		for(int j=1;j<i;j++)
			if(Num[j]>=Num[i]) F[i]=Max(F[i],F[j]+1);
		Ans=Max(Ans,F[i]); 
	} printf("%d\n",Ans); Ans=0;
	memset(F,0,sizeof(F));
	/*
	for(int i=1;i<=N;i++)
	{
		F[i]=1;
		for(int j=1;j<i;j++)
			if(Num[j]<Num[i]) F[i]=Max(F[i],F[j]+1);
		Ans=Max(Ans,F[i]);
	} printf("%d\n",Ans);*/
	for(int i=1;i<=N;i++)
	{
		if(F[i]) continue;
		F[i]=1; now=Num[i];Ans++;
		for(int j=i+1;j<=N;j++)
		{
			if(F[j]) continue;
			if(now<Num[j]) continue;
			F[j]=1; now=Num[j]; 
		} 
	}
	printf("%d\n",Ans);
	return 0;
}