题目地址：http://www.rqnoj.cn/Problem_217.html

题目:[NOIP1999]拦截导弹

问题编号:217

题目描述

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入格式

输入数据为两行，
第一行为导弹的数目N(n<=1000)
第二行导弹依次飞来的高度，所有高度值均为不大于30000的正整数。

输出格式

输出只有一行是这套系统最多能拦截的导弹数和要拦截所有导弹最少要配备这种导弹拦截系统的套数。两个数据之间用一个空格隔开.

样例输入

8
389 207 155 300 299 170 158 65

样例输出

6 2

题目的意思以经说的很清楚了，就是有一套导弹系统，它可以打到任意高度，但是下一发只能打比这一发高度低的导弹，是严格低。现在给你一串导弹的高度，问你一套导弹最多可以打多少，以及如果要把所有的导弹打到，得至少多少套这样的导弹系统。首先是思考第一问，因为每次能打的导弹高度智能比前一次的低，那么我能够打到的最多次数的那一串导弹序列的高度肯定是严格递减的，所以这一问就变成了我们要在这一串导弹里面求出一个最长递减子序列的长度。然后是第二问，要求把所有的导弹能够打到，至少要多少导弹系统。假设存在一个最长非下降子序列，则子序列里面的导弹是不能在一个系统里面的，这个可以反证，因为如果他们可以在一个系统里的话，那么显然与题意是矛盾的（感谢李伟强同学的点拨，这样一说就通了），所以那么至少要多少套系统的数量就是求一个最长非下降子序列的长度就OK了。

用f1[i]  表示以i为尾巴最长递减子序列的长度

用f2[i]  表示以i为尾巴最长非递减子序列的长度

状态转移方程如下：

f1[i] = max(f1[j]+1) 0<=j<i && num[i]<num[j]   //严格递减的

f2[i] = max(f2[j]+1) 0<=j<i && num[i]>=num[j]  //非递减

在赋初值的时候也要注意，我们第一次将num[0] = 无穷大 第二次将num[i] = -1，因为两次的单调性不一样

#include<iostream>
#include<stdlib.h>
using namespace std;
#define MAX 10010

int main()
{
	int f[MAX];
	int num[MAX];
	int t;
	int m;

	//cin>>t;
	while(cin>>m && m)
	{
		//cin>>m;
		int i,j;
		for(i=1;i<=m;i++)
		{
			cin>>num[i];
		}

		
		//求最长递减子序列
		for(i=0;i<=m;i++)
			f[i] = 0;
		num[0] = 100000000;
		int max1=0;     //max1用来保存最长递减，max2用来保存最长非降 
		for(i=1;i<=m;i++) 
		{
			for(j=i-1;j>=0;j--)
			{
				if(num[j]>num[i] && f[j]+1>f[i])
					f[i] = f[j]+1;
			}
			if(max1<f[i])
				max1 = f[i];
		}
		

		//求最长非降子序列
		for(i=0;i<=m;i++)
			f[i] = 0;
		int max2 = 0;
		num[0] = -1;
		for(i=1;i<=m;i++)
		{
			for(j=i-1;j>=0;j--)
			{
				if(num[j]<=num[i] && f[j]+1>f[i])
					f[i] = f[j]+1;
			}
			if(max2<f[i])
				max2 = f[i];
		}
		
		cout<<max1<<" "<<max2<<endl;
	}

	return 0;
}