1.4　导弹拦截

【题目描述】 导弹拦截（missile）

A国开发出一套导弹拦截系统，这套导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹的高度都不能高于前一发炮弹的高度。某天，A国雷达捕捉到B国的导弹来袭，但由于该系统还在试用阶段，且只有一套，因此有可能不能拦截所有的导弹。

计算这套系统最多能拦截多少导弹。如果要拦截所有的导弹，则最少要配备多少套这种导弹拦截系统？

【输入格式】

在一行中输入若干个整数（整数个数≤100 000），用来表示每个导弹在空中的高度（雷达给出的高度数据是不大于30 000 的正整数）。

【输出格式】

在一行中输出两个整数，第一个整数表示这套系统最多能拦截多少导弹，第二个整数表示要拦截所有导弹最少要配备多少套这种导弹拦截系统。

【输入样例】

389 207 155 300 299 170 158 65

【输出样例】

6 2

【样例说明】

6为最多能拦截的导弹数，2为要拦截所有导弹最少要配备的导弹拦截系统套数。

【算法分析】

第一问是经典的动态规划问题──求最长不上升子序列。

比较难的是第二问，如果用最直观的贪心算法，也许能通过一些测试数据，但也很容易找到反例。例如6 5 1 7 3 2，如果第一次选择最长序列6 5 3 2发射炮弹，则剩下的1和7还需再发射炮弹两次才能打到。而最好的方案应该是6 5 1和7 3 2。

由此可见，因为每个导弹都要打到，故应该把注意力放在“打到每一个导弹”上。在上一个例子中，7是必须打到的，因为它是最高的，所以必有一次拦截是以7开头的。

既然是必须打的，那么打7的同时可以顺便打一打其他的。打哪些呢？答案应该是打后面的导弹中最高的一个，这里设为K。打K等于是“白打”，而对于7和K之间的导弹，如果打了任何一个就一定不能再打K了（因为K最高）。

类似地，下一个目标是K后面的导弹中的最高的。

实际上，该题第二问最简单的解法是使用Dilworth定理：一个序列中不上升子序列的最小覆盖数等于序列中最长不下降序列的长度。