首页 > 试题广场 >

拦截导弹

[编程题]拦截导弹

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

某国为了防御敌国的导弹袭击，开发出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，并观测到导弹依次飞来的高度，请计算这套系统最多能拦截多少导弹。拦截来袭导弹时，必须按来袭导弹袭击的时间顺序，不允许先拦截后面的导弹，再拦截前面的导弹。

输入描述:

每组输入有两行，
第一行，输入雷达捕捉到的敌国导弹的数量k（k<=25），
第二行，输入k个正整数，表示k枚导弹的高度，按来袭导弹的袭击时间顺序给出，以空格分隔。

输出描述:

每组输出只有一行，包含一个整数，表示最多能拦截多少枚导弹。

示例1

输入

8
300 207 155 300 299 170 158 65

输出

算法知识视频讲解

大内高手

发表于 2020-03-17 17:10:08

// runtime: 4ms // space: 504K #include <iostream> #include <cstdio> using namespace std; const int MAX = 25; int arr[MAX]; int dp[MAX]; 展开全文

Coming680

发表于 2022-02-12 12:53:10

#include<iostream> using namespace std; int main() { int k,ans = 0; int height[25]{0},dp[25]; cin >> k; for(int i = 0;i &l 展开全文

牛客440904392号

发表于 2024-10-02 12:07:00

#include <iostream> using namespace std; int main() { int k; cin >> k; int nums[k]; for (int i = 0; i < k; i++) cin > 展开全文

辣椒味的糖葫芦

发表于 2023-03-18 18:36:08

n = int(input()) num = list(map(int, input().split(" "))) dp = [1 for i in range(n)] # 初始为1 for i in range(n): for j in range(i): if num[ 展开全文

azzz1112

发表于 2024-03-15 14:46:31

import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner scanner 展开全文

爱喝零度可乐

发表于 2023-03-16 20:09:41

#include<cstdio> #include<iostream> #define N 25 using namespace std; int main() { int n; int ans = 0; int dp[N]; int heig 展开全文

阿尔芒a

发表于 2024-03-21 21:46:46

//dfs秒了 #include<iostream> #include <cstdio> #include <string> #include <algorithm> #include<vector> using namespace std 展开全文

Huster水仙

发表于 2023-02-10 14:31:50

最长递减子序列（不一定连续）：DP 思路：统计以s[i]结尾的递减子序列的最大长度dp[i] 分为2类：是否比前面所有元素都大 ①是前面序列对其没有贡献:lenth[i]=1 ②否前面序列对其有贡献:dp[i]=max(dp[j]+1 )（需遍历s[i]前面所有元素，保留最大值） #incl 展开全文