【动态规划, 贪心】拦截导弹「动态规划之LIS模型」

题目

1010. 拦截导弹 - AcWing题库

---

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

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

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

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

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

输入格式

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

输出格式

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

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

数据范围

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

输入样例：

389 207 155 300 299 170 158 65

输出样例：

6
2

解题

方法一：动态规划 贪心算法

思路

第一问求序列的最长【不升】子序列，直接套模板即可。

第二问是求该序列最少可以拆分成多少个不升子序列，用到贪心算法。

贪心策略

从前往后扫描每个数，对于每个数：

• 如果存在结尾大于等于当前数的子序列，则把该数加入结尾大于等于该数的最小的子序列后面；
• 如果现有的子序列结尾都小于当前数，则创建新的子序列以放入该数。

证明

见 1.2.2 最长上升子序列模型（二） - AcWing 中 19:06 处。

代码

import java.util.*;
import java.io.*;

public class Main {
    static final int N = 1010;
    static int[] a = new int[N];
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        int n = 0;
        for (; in.nextToken() != in.TT_EOF; ++n) a[n] = (int) in.nval;
        int[] f = new int[n];
        int mx = 1;
        for (int i = 0; i < n; ++i) {
            f[i] = 1;
            for (int j = 0; j < i; ++j) {
                if (a[j] >= a[i]) f[i] = Math.max(f[i], f[j] + 1);
            }
            mx = Math.max(mx, f[i]);
        }      
        System.out.println(mx);
        // 第二问开始
        int[] g = new int[n]; // 用于存放子序列的结尾
        int cnt = 0; // 子序列的数量
        for (int i = 0; i < n; ++i) {
            int j = 0;
            // 扫描现存子序列 查找是否存在结尾大于等于当前数的子序列
            // 由于不升子序列是以以上的贪心策略依次加入g中的 所以g中的子序列结尾一定是非递增的
            // 导致如果能找到结尾大于等于该数的子序列 那它一定是满足条件的最小结尾子序列
            while (j < cnt && a[i] > g[j]) ++j;
            if (j < cnt) g[j] = a[i]; // 如果存在 则把该数加入结尾大于等于该数的最小的子序列后面
            else g[cnt++] = a[i]; // 否则维护一个新的子序列来放它
        }
        System.out.println(cnt);
    }
}