首页 > 试题广场 >

拦截导弹

[编程题]拦截导弹

热度指数：4535 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以只一套系统，因此有可能不能拦截所有的导弹。

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

数据范围：导弹个数 n 满足 $1 \le n \le 1000 \$ ，导弹的高度 m 满足 $1 \le m \le 1000 \$

输入描述:

第一行输入一个正整数 n ，表示导弹的个数
第二行输入 n 个正整数，表示导弹的高度

输出描述:

输出一套拦截系统最多拦截多少导弹和最少要配备多少套导弹拦截系统两个正整数

示例1

输入

8
389 207 155 300 299 170 158 65

输出

6
2

算法知识视频讲解

-含章可贞-

发表于 2022-05-16 14:19:20

Q1：很明确就是最长递减子序列的长度 Q2：根据Dilworth定理:最少的下降序列个数就等于整个序列最长上升子序列的长度 n=eval(input()) heights=list(map(int,input().split())) dp=[1]*n # Q1:最长递减子序列 dp2=[1]*n # 展开全文

Sousey

发表于 2022-03-03 18:06:50

动态规划(C++) 这道题学到了一个很吊的知识： Dilworth定理: 最少的下降序列个数就等于整个序列最长上升子序列的长度下面这个是知识博客链接 https://blog.csdn.net/litble/article/details/85305561?ops_request_misc=& 展开全文

想去东北泡澡的本杰明在敲键盘

发表于 2022-07-31 01:50:13

import java.util.*; public class Main { static int n; public static void main(String[] args) { Scanner in = new Scanner(System.in); 展开全文

充电中...

发表于 2022-07-01 10:34:31

C写的 #include <stdio.h> int main(){ int n = 0; scanf("%d",&n); int arr[n]; int d 展开全文

苏庆栋

发表于 2022-02-14 14:57:19

第一问没什么说的，跟DP9 一样，就是改成了下降序列。第二问求个数，由于没思路，查题解查到了一个Dilworth定理偏序集能划分成的最少的全序集个数等于最大反链的元素个数。查到的一个比较好的博客对本题，第二问就是求该序列“严格上升子序列最大长度”，这个数就等于所求的下降序列个数 #incl 展开全文

吱吱1111111

发表于 2024-04-22 03:02:41

Dilworth定理:最少的下降序列个数就等于整个序列最长上升子序列的长度大部分答案都是基于这个，但这个数学定理还蛮冷门的，临时遇到肯定不会做，所以再多写了一个暴力解求最长递减子序列还是用传统dp同时用一系列队列来模拟排队过程策略是拿到一个数字看看已有队列能不能放下它如果有，把它放在队尾数字最小的队展开全文

温稚

发表于 2023-10-12 16:54:25

Dilworth定理: 最少的下降序列个数就等于整个序列最长上升子序列的长度 //本题用动态规划求解，合唱队那题很有参考价值，可以参考我上一篇题解 // 本题思路求出最长递减子序列即为一次最多拦截导弹数逆向思维求反方向的最长递增子序列 // if (inits[i] >= ini 展开全文

喜欢修勾的托尼也不容易

发表于 2022-04-07 20:41:56

该题两问分开做的，第一个用了动规，max_num数组下标为i的元素表示第i个导弹是某个系统的第max_num[i]发炮弹，如果前i发炮弹中某个第j发炮弹的最低高度并且比当前炮弹高，那么第i发炮弹就在第j发炮弹之后进行拦截，即max_num[i]= max_num[j]+1。max_num中的最大值即展开全文