题目描述
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入
每个测试文件只包含一组测试数据，每组输入若干个整数，表示导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数）。
输出
对于每组输入数据，第一行输出这套系统最多能拦截多少导弹，第二行输出如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。
样例输入 复制
389 207 155 300 299 170 158 65样例输出 复制
6
2
**************************************************************************************************************
这一题就是一个DP，本质上就是为了求最长子序列（升）和最长子序列（降）。最长降子序列长度就是题上要的一个系统能拦截的最大个数，而拦截所有导弹所要的最少系统数就是最长升序列的长度，因为升序列每一个元素都是该总序列的分界点，知道就行，做题会用就好。
动态规划，自己模拟一下过程理解的更快。
该算法的时间是o(n^2);
*************************************************************************************************************
#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
int o[999999];
int dd[99999],dx[99999];
int main(void)
{int n=0;while(cin>>o[n++]);//cin的多实例不需要EOF就是^z结束n--;//把^z输入了所以需要减一for(int i=0;i<n;i++)//至少它本身是一个序列，所以最短序列长度为1.dd[i]=1,dx[i]=1;for(int i=0;i<n;i++)for(int j=0;j<i;j++){if(o[j]>=o[i])dx[i]=max(dx[j]+1,dx[i]);//更新到该点的降序列最大长度，elsedd[i]=max(dd[j]+1,dd[i]);//更新到该点的升序列最大长度，}int maxi=0,maxj=0;for(int i=0;i<n;i++)//找出最大序列长度{maxi=max(maxi,dx[i]);maxj=max(maxj,dd[i]);}cout<<maxi<<" "<<maxj<<endl;return 0;
}