$$\color{Red}{拦截导弹=贪心+单调栈}$$

这里附带打个广告——————我做的所有的题解

包括基础提高以及一些零散刷的各种各样的题

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。

但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。

某天，雷达捕捉到敌国的导弹来袭。

由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。

输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数，导弹数不超过1000），计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统。

输入格式

共一行，输入导弹依次飞来的高度。

输出格式

第一行包含一个整数，表示最多能拦截的导弹数。

第二行包含一个整数，表示要拦截所有导弹最少要配备的系统数。

数据范围

雷达给出的高度数据是不大于 30000 的正整数，导弹数不超过 1000

输入样例：

389 207 155 300 299 170 158 65

输出样例：

6
2

证明

本题分为两问，第一问明显是最长下降子序列，只不过可以相等，模板加入等号即可。

第二问至少多少个这样的序列组，其思想为贪心思路。参考与nlogn的最长上升子序列2 的做法，也很接近区间分组 ，思路是接近的，由于我们这道题是维护递增的组右端值，所以适合用二分的方法，或者用分组的小根堆也可以。

具体思路

1. 先声明一个空的队列，存储每组下降子序列的右端点

2. 遍历整个序列，一旦序列元素的值，大于队列任何一个元素的值，那么显然它无法接到这些分组后面，将他加入队列中，相当于一个单独的分组

3. 一旦序列元素的值，小于队列中右端点的值，那么就将它放到满足小于它的同时是队列中最小的那个分组里面（贪心，更容易让大值被充分利用），这里放入的方法和之前 最长上升子序列2一样，采用二分搜索第一个大于等于它的元素，进行替代关系

4. 最后序列的元素长度即分组的最小数目，显然此时队列应该是一个递增的序列，因为只有大了，才能生成在队列尾部

java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int N = 1010, n;
    static int[] f = new int[N];
    static int[] a = new int[N];
    static int[] stk = new int[N];
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {
        String [] str = br.readLine().split(" ");
        n = str.length;
        // 最长下降子序列
        int res = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = Integer.parseInt(str[i-1]);
            f[i] = 1;
            for (int j = 1; j < i; j++) {
                if (a[i] <= a[j])
                    f[i] = Math.max(f[i], f[j] + 1);
            }
            res = Math.max(res, f[i]);
        }
        System.out.println(res);
        // 贪心求导弹数目
        int tt = 1;
        stk[1] = a[1];
        for (int i = 2; i <= n; i++) {
            if (a[i] > stk[tt])
                stk[++tt] = a[i];
            else{
                int l = 1, r = tt;
                while(l < r){
                    int mid = l + r >> 1;
                    if (stk[mid] < a[i]) l = mid + 1;
                    else r = mid;
                }
                stk[l] = a[i];
            }
        }
        System.out.println(tt);
    }
}

python

a = [0] + [int(x) for x in input().split()]
n = len(a) - 1
N = 1010
f = [1] * N
q = [0] * N

res = 0
for i in range(1, n+1):
    for j in range(1, i):
        if a[i] <= a[j]:
            f[i] = max(f[i], f[j] + 1)
    res = max(f[i], res)

print(res)

cnt = 1
q[1] = a[1]
for i in range(2, n+1):
    if q[cnt] >= a[i]:
        l, r = 1, cnt
        while l < r:
            mid = l + r >> 1
            if q[mid] < a[i]:
                l = mid + 1
            else:
                r = mid
        q[l] = a[i]
    else:
        cnt += 1
        q[cnt] = a[i]

print(cnt)