好久没有更新了，今天带来的是P1020 [NOIP 1999 提高组] 导弹拦截，一道线性动态规划题，题目读起来比较简单，如果是用肉眼去找好像不是很难，但如何让计算机实现呢。

先放一下样例，389 207 155 300 299 170 158 65。如果是要拦截这些导弹，因为以后每一发炮弹都不能高于前一发的高度，所以我们要找一个尽量最大的并且尽量在前面的。而389 300 299 170 158 65就是最长的能满足题目要求的拦截情况，这是一个最长不上升序列，就把第一问转变成求最长不上升序列的问题。

而对于第二问，要求的是最少需要几套系统来拦截，可以看到因为最长的也不能全部拦截，所以肯定是需要两套以上的，而两套389 207 155 | 300 299 170 158 65就可以满足。那么最少就是两套，那么这是要求什么呢，因为是个数。所以是求最少的不上升序列的个数。求这个好像没有什么直接求的方法，这时候就需要一点组合数学里的知识。我们知道偏序集的定义是设R是集合A上的一个关系，如果R是自反的、反对称的和可传递的，则称R是集合A的偏序关系，简称偏序，记作“≤”。对于（a，b）∈R，就把它表示成a≤b。若在集合A上给定一个偏序关系≤，则称集合A按偏序关系≤构成一个偏序集合，集合A和偏序R一起称为偏序集，记作（A，≤）。而不上升序列就是一个，偏序关系为前面的数大于等于后面的数的偏序集。那么在偏序集里有一个Dilworth定理，对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。此定理的对偶形式亦真，它断言：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目。那么求最长上升序列中数的个数就可以得到最少的上升序列的数量，因为上升和不上升显然是反链。

由此，对计算机来说，一个是求最长不上升序列，一个是求最长上升序列。贴一下代码。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> heights;
    int num;
    while (cin >> num) {
        heights.push_back(num);
    }
    
    int n = heights.size();
    if (n == 0) {
        cout << "0\n0\n";
        return 0;
    }
    
    // 第一问：最长不上升子序列
    vector<int> d;
    for (int i = 0; i < n; ++i) {
        if (d.empty() || heights[i] <= d.back()) {
            d.push_back(heights[i]);
        } else {
            auto it = upper_bound(d.begin(), d.end(), heights[i], greater<int>());
            *it = heights[i];
        }
    }
    cout << d.size() << endl;
    
    // 第二问：最长上升子序列
    vector<int> f;
    for (int i = 0; i < n; ++i) {
        if (f.empty() || heights[i] > f.back()) {
            f.push_back(heights[i]);
        } else {
            auto it = lower_bound(f.begin(), f.end(), heights[i]);
            *it = heights[i];
        }
    }
    cout << f.size() << endl;
    
    return 0;
}

首先是把全部的数都读取进去，但是本题并没有告诉我们数据有多少个，那么如何确保把全部数都读取进去，cin这个函数，本身就会对是否读取到数据进行判断，如果有就会输出true，没有就会输出false，这样就可以保证都读取到。

然后就是求最长序列了，求不上升和上升的结构都是一样的，在求的过程中用到了upper_bound和lower_bound这两个函数，这两个函数的作用是用二分查找在指定序列找到第一个大于或小于比较值的数的位置。在寻找最长序列的过程中，以寻找不上升子序列为例，如果下一个数比当前末尾数小，那么毫无疑问可以添加到末尾。但如果比当前末尾数大时，那么当前的序列有可能就不是最长的，那么就需要对当前的序列进行处理，在序列中找到第一个比比较值小的数进行替换，此时不会影响序列的有序性，也不会影响序列的长度，但这样不会影响之后遇到比被替换数大但比比较值小数无法加入序列。通过这个规则遍历全部的数就能得到最长序列。