【线性DP】飞弹拦截

题目

试题 算法提高 飞弹拦截

---

强大的 kAc 建立了强大的帝国，但人民深受其学霸及 23 文化的压迫，于是勇敢的高达决心反抗。

高达能远程发飞弹打击，他先后对着城市开了 $n$ 发，第 $i$ 个飞弹高度为 $h_i$ 。然而 kAc 帝国也有一门炮可以拦截高达发射的飞弹，虽然拦截成功率为 $100\%$ ，但由于技术问题，这门炮每次只能拦截比上一次高度相同或更高的飞弹（第一次可以拦截任意飞弹）。玛德go负责此次拦截，他刚算好拦截方案又接到了上级的任务：一些给定的飞弹由于杀伤力大必须拦截。玛德go显然已经不屑于解决这种问题了，他显然要做一些更有意义的事情。于是这问题就交给了你，在打掉指定飞弹的前提下打掉最多飞弹。

输入

第一行一个数 $n$ ，第二行 $n$ 个数，依次表示飞来的飞弹高度。

第三行一个数 $m$ ，表示必须拦截的飞弹个数，第四行 $m$ 个数表示这些飞弹的编号（ $0$ 到 $n-1$ ），并且保证单调递增，保证存在至少一种打击方案。

输出

一个数表示最多打掉的飞弹。

样例输入

5
2 4 3 4 5
2
1 3

样例输出

4

数据规模和约定

• $30\%$ 的数据 $n\le10$
• $70\%$ 的数据 $n\le100$
• $100\%$ 的数据 $n\le1000, m\le100$
• 飞弹的高度在 int 表示范围内

解题

方法一：动态规划

思路

本题是一个基于 LIS 模型的线性DP问题，状态定义和状态转移都和 LIS 问题一样，不过对状态转移过来的条件有所限制。

动态规划：

• 状态定义： $f[i]$ 表示只考虑前 $i$ 个飞弹时所有拦截方案中的最大拦截数量；

• 状态转移：当 $a[j] \le a[i]$ 时， $f[i] = \max(f[i], f[j] + 1)$ ， $j$ 需要满足的条件：

  • 在 $i \le {}$ 第一个必须拦截的飞弹时： $j = 0 \dots i - 1$ ；
  • 在 $i > {}$ 第一个必须拦截的飞弹时：
    • 当 $i$ 为必须拦截的飞弹时： $j = 上一个必须拦截的飞弹 \dots i - 1$ ；
    • 否则：$j = 上一个必须拦截的飞弹 \dots i - 1$ 且 $f[j] > 1$ 。

• 初始状态： $f[0 \dots n - 1] = 1$ 。

代码

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

public class Main {
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); int n = (int) in.nval;
        int[] a = new int[n];
        for (int i = 0; i < n; ++i) {
            in.nextToken(); a[i] = (int) in.nval;
        }
        in.nextToken(); int m = (int) in.nval;
        boolean[] must = new boolean[n];
        while (m-- > 0) {
            in.nextToken(); int x = (int) in.nval;
            must[x] = true;
        }
        int[] f = new int[n];
        int prev = 0;
        for (int i = 0; i < n; ++i) {
            f[i] = 1;
            for (int j = prev; j < i; ++j) {
                if (prev > 0 && f[j] == 1 && !must[j]) continue;
                if (a[j] <= a[i]) f[i] = Math.max(f[i], f[j] + 1);
            }
            if (must[i]) prev = i;
        }
        int ans = 0;
        for (int i = prev; i < n; ++i) ans = Math.max(ans, f[i]);
        System.out.println(ans);
    }
}