记录编号	44937	评测结果	AAAAAAAAAA
题目名称	导弹系统	最终得分	100
用户昵称	Truth.Cirno	是否通过	通过
代码语言	C++	运行时间	0.061 s
提交时间	2012-10-21 13:09:25	内存使用	4.29 MiB

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

int a[100010],f[2][100010];

int maxint(int a,int b)
{
	if (a>b)
		return(a);
	return(b);
}

int main(void)
{
	freopen("missilea.in","r",stdin);
	freopen("missilea.out","w",stdout);
	int i,j,n;
	while (scanf("%d",&n)==1)
	{
		if (n==0)
			break;
		for (i=1;i<=n;i++)
			scanf("%d",&a[i]);
		f[1][1]=1;
		f[0][1]=0;
		for (i=2;i<=n;i++)
		{
			f[1][i]=1;
			f[0][i]=0;
			for (j=1;j<i;j++)
			{
				if (a[i]>a[j]&&f[0][j])
					f[1][i]=maxint(f[1][i],f[0][j]+1);
			}
			for (j=1;j<i;j++)
			{
				if (a[i]<a[j]&&f[1][j])
					f[0][i]=maxint(f[0][i],f[1][j]+1);
			}
		}
		printf("%d\n",maxint(f[0][n],f[1][n]));
	}
	return(0);
}