先看题目：https://ac.nowcoder.com/acm/problem/16810
题目描述：
有一个导弹系统，每一发炮弹都不能高于前一发的高度。第一问是问能拦截多少导弹？第二问是问要拦截所有导弹最少需要多少套这样的导弹系统？
解题思路：
第一问就是求序列的最长不上升子序列。
第二问我的思路是：整个序列中递增的那些数肯定是被不同的导弹系统拦截，那么求出最长上升子序列的长度就完了呗，
这里稍严谨点，引入Dilworth定理。
Dilworth定理说了什么一件事呢？
一个数列划分成最少的不升子序列的数目就等于这个数列的最长上升子序列的长度

不上升子序列就是导弹系统。
要拦截所有导弹最少需要多少套这样的导弹系统 就是 数列划分成最少的不升子序列的数目

代码：

#include<bits/stdc++.h>
using namespace std;
int a[100010];
int dp1[100010];
int dp2[100010];
int main()
{
    int n = 1;
    while(scanf("%d",&a[n])!=EOF) n++;
    n-=1;
    dp1[1]=a[1]; int len=1;
    for(int i = 2; i <= n; i++) {
        if(a[i] <= dp1[len]) {
            dp1[++len] = a[i];
        }
        else {
            int m = upper_bound(dp1+1, dp1+len+1, a[i], greater<int>()) - dp1;
            dp1[m] = a[i];
        }
    }
    printf("%d\n",len);
    dp2[1]=a[1]; len = 1;
    for(int i = 2; i <= n; i++) {
        if(a[i] > dp2[len]) {
            dp2[++len] = a[i];
        }
        else{
            int m = lower_bound(dp2+1, dp2+len+1, a[i]) - dp2;
            dp2[m] = a[i];
        }
    }
    printf("%d\n",len);
}