题目大意:
为了拦截敌国的袭击，科学家研发出一套导弹系统，导弹系统有个缺陷：第一发炮弹可以到达任意高度，然而之后的每一发炮弹都不能高于前一发的高度。
现给出数个导弹的高度( <=50000的正整数 )：
389,207,155,300,299,170,158,65，
计算一套导弹拦截系统最多可以拦截多少导弹，如果需要拦截全部导弹需要多少套导弹拦截系统？

这题是一道LIS模板题,第一问很好想到就是求最长的非递增序列,但是第二问不好想。
LIS（Longest Increasing Subsequence）动态规划思路：
先不考虑题目，单求最长上升子序列（不含相等）。
简单案例：1，3，2，6，4，5
（下面的长度即是最优解的意思）
1处的长度显然为1；
3处显然是1的长度+1；
2处是1处长度+1；
6处是3处（或2处）长度+1；
4处是3处（或2处）+1；
5处是4处+1（而不是2、或3）；
显然，后面的元素对应最优解是前面小于该元素中最优解最大的+1；
有如此的状态转移方程：
dp[i] = max(dp[j]+1)；/代码中要变通 / （ 0 <= j < i ）；

个人对第二问的理解：
个人不是很懂原理，只能借助图像来辅助理解（太菜了）：

（图画的不好hh。。）
①号线的长度：2，是原题目的情况下，需要的导弹次数；
可以这么理解，如果长度为1，代表左边的207和155不存在，现在既然存在了，代表需要多一个导弹系统，另外处理这两个导弹了，（长度刚刚好就是2。。）。

②号线的长度为：3，显然，不能跟第一次一起拦截，也不能和前面的 207和 155一起处理，刚好长度是3（因为有160的存在才多了一个）。

代码（走案例）：

#include<iostream>
using namespace std;
#define __max(a,b) (((a) > (b)) ? (a) : (b))
#define N 8
int H[9] = {389,207,155,300,299,170,158,65};
int up[9];//最长上升序列,不含=
int down[9];//最长下降序列,含=
int main()
{
    int len_up = 0/*第二问*/, len_down = 0/*第一问*/;
    for (int i = 1; i <= N ; i++)
    {
        up[i] = 0;
        down[i] = 0;
        for(int j = 0 ; j < i ; j++)
        {
            if(H[j]/*H[j]不比H[i]小*/ >= H[i])
            {
                down[i] = __max(down[j]+1,down[i]);
            }
            if(H[j]/*H[j]比H[i]小*/ < H[i])
            {
                up[i] = __max(up[j]+1,up[i]);/*取j中up[j]最大的*/
            }
        }
        // printf("高度%d ,up : %d\n",H[i],up[i]);
        len_up = __max(up[i],len_up);
        len_down = __max(down[i],len_down);
    }
    printf("%d\n%d",len_down,len_up);
    return 0;   
}

（蓝桥杯备赛笔记）