侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【线性DP】飞弹拦截

GabrielxD
2023-04-15 / 0 评论 / 0 点赞 / 322 阅读 / 985 字
温馨提示:
本文最后更新于 2023-04-17,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

试题 算法提高 飞弹拦截


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

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

输入

第一行一个数 nn ,第二行 nn 个数,依次表示飞来的飞弹高度。

第三行一个数 mm ,表示必须拦截的飞弹个数,第四行 mm 个数表示这些飞弹的编号( 00n1n-1 ),并且保证单调递增,保证存在至少一种打击方案。

输出

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

样例输入

5
2 4 3 4 5
2
1 3

样例输出

4

数据规模和约定

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

解题

方法一:动态规划

思路

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

动态规划:

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

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

    • ii \le {} 第一个必须拦截的飞弹时: j=0i1j = 0 \dots i - 1
    • i>i > {} 第一个必须拦截的飞弹时:
      • ii 为必须拦截的飞弹时: j=上一个必须拦截的飞弹i1j = 上一个必须拦截的飞弹 \dots i - 1
      • 否则:j=上一个必须拦截的飞弹i1j = 上一个必须拦截的飞弹 \dots i - 1f[j]>1f[j] > 1
  • 初始状态: f[0n1]=1f[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);
    }
}

0

评论区