用java解决以下题目:某国为了防御敌国的导弹袭击开发出了一种导弹拦截系统但是这种拦截系统有一个缺陷:虽然它的第一发炮弹能够到达任意的高度但是以后每一发炮弹都不能高于前一发的高度。某天雷达捕捉到敌国的导弹来袭由于该系统还在试用阶段。所以一套系统有可能不能拦截所有的导弹输入导弹依次飞来的高度雷达给出的高度不大于30000的正整数。计算要拦截所有导弹最小需要配备多少套这种导弹拦截系统
思路:
1.首先,我们需要定义一个数组来存储导弹依次飞来的高度。
2.然后,我们需要找出最长的不上升子序列,也就是最多能拦截多少导弹。
3.最后,我们将拦截导弹的个数与数组的长度作比较,得出需要配备多少套导弹拦截系统。
代码实现:
import java.util.Scanner;
public class MissileInterceptionSystem {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int[] height = new int[30001];
int count = 0;
while (input.hasNextInt()) {
height[count++] = input.nextInt();
}
int[] dp = new int[count];
int max = 0;
for (int i = 0; i < count; i++) {
dp[i] = 1;
for (int j = 0; j < i; j++) {
if (height[j] >= height[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
max = Math.max(max, dp[i]);
}
System.out.println(max);
System.out.println(count - max);
}
原文地址: https://www.cveoy.top/t/topic/fjIN 著作权归作者所有。请勿转载和采集!