这道题目是我思考了很久的一道题目，可能是因为我太弱了吧。我们先来分析题目。
第一问
这一问是求一套系统能最大拦截的导弹数量。抽象化后，我们可以得出，其实这一问就是让我们求这个序列中最长的不上升序列。我们先来分析样例输入。
389 207 155 300 299 170 158 65
显然，对于这个序列，他的最长不上升序列是 \(389,300,299,170,158,65\)。那么，我们如何用最佳的算法求出此子序列呢？
贪心策略
我们先设定一个指向变量 cursor = 0，这个变量记录当前算法在序列S中的位置。我们再设定一个 pos = 0 的变量，记录我们子序列H的尾部位置。
如果S[cursor]>H[pos]，我们可以直接把 S[cursor] 置于 H 的尾部，即 H[++pos] = S[cursor]。而如果不是这样，我们则可以在 H[0:pos]，即 0 到 pos 这段区间内，总可以找到第一个小于 S[cursor] 的的量（事实上，我们可以使用二分搜索来查找这个量，因为序列 H 是拍好了顺序的），我们就让 H[bias] = S[cursor]。反复如此。
为什么要把第一个在序列 H 中小于 S[cursor] 的赋为 S[cursor]？因为当我们把这个值赋入后，我们后续需要插入数据的时候，便会更容易地加入数字（因为在相同位置下，值越大，后续加入的数字的限制也会缩小），也就会使这个子序列最长。
而如果我们要追求 \(\Theta(n \log n)\) 的做法时，便需要二分查找。接下来我来介绍两个函数。
lower_bound(start, end, key, [cmp])
该函数调用后会返回一个有序序列中第一个大于等于（如果有 cmp 函数传入，那就是另外一回事）key 的元素地址。
upper_bound(start, end, key, [cmp])
该函数调用后会返回一个有序序列中第一个大于（如果有 cmp 函数传入，那就是另外一回事）key 的元素地址。
奇怪的是，这两个函数跟字面上的完全不同，upper_bound 和 lower_bound 在没有 cmp 参数传入的情况下，默认的序列排序情况是一致的。搭配之后，便可以获得 \(\Theta(n \log n)\)的神奇速度。
第二问
Dilworth 定理
在一个数字序列中，最大不上升子序列的个数为最大上升子序列的长度。亦而反之。
对于我这种蒟蒻而言，Dilworth 定理能帮助到我的只是这句话。我曾经翻阅过很多博客，也翻阅过《组合数学》，我并没有找到易于理解的语句。而在我翻阅到一篇绝世神作之后，我便把我的理解归于这一句话。对于 OIer 而言，Dilworth 最有力的部分便是这句话了。
解题思路
第二问的疑问是求出导弹防御系统的套数，根据 Dilworth 定理，套数应该等于最大不下降子序列的长度。所以，按照第一问的贪心思路，我们很容易类比出本题求最大不上升子序列的贪心策略。所以，在这里，我便不再赘述。