记录编号	43387	评测结果	AAAAA
题目名称	[NOIP 1999]拦截导弹	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2012-10-10 09:07:41	内存使用	2.08 MiB

#include <cstdio>
using namespace std;

int mis[10000],len[10000],dad[10000];
bool used[10000];

int main(void)
{
	freopen("missile.in","r",stdin);
	freopen("missile.out","w",stdout);
	int i,j,n=1,rest,maxlen,maxlenpos,c=0,from,temp;
	while (scanf("%d",&mis[n])==1)
		n++;
	n--;
	rest=n;
	/*assign*/
	for (i=1;i<=n;i++)
	{
		len[i]=0;
		dad[i]=0;
	}
	/*assign*/
	for (i=1;i<=n;i++)
	{
		maxlen=0;
		for (j=i-1;j>=1;j--)
		{
			if (mis[j]>=mis[i]&&len[j]>maxlen)
			{
				maxlen=len[j];
				maxlenpos=j;
			}
		}
		len[i]=maxlen+1;
		dad[i]=maxlenpos;
	}
	maxlen=0;
	for (i=1;i<=n;i++)
		if (len[i]>maxlen)
			maxlen=len[i];
	printf("%d\n",maxlen);
	rest=n;
	while (rest)
	{
		c++;
		for (i=1;i<=n;i++)
			if (!used[i])
			{
				from=i;
				break;
			}
		used[from]=true;
		temp=mis[from];
		rest--;
		for (i=from+1;i<=n;i++)
		{
			if (used[i])
				continue;
			if (temp>=mis[i])
			{
				used[i]=true;
				temp=mis[i];
				rest--;
			}
		}
	}
	printf("%d\n",c);
	fclose(stdin);
	fclose(stdout);
	return(0);
}