侧边栏壁纸
博主头像
GabrielxD

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

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

目 录CONTENT

文章目录

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

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

题目

1010. 拦截导弹 - AcWing题库


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

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

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

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

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

输入格式

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

输出格式

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

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

数据范围

雷达给出的高度数据是不大于 3000030000 的正整数,导弹数不超过 10001000

输入样例:

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);
    }
}
0

评论区