Java 导弹拦截系统：最少拦截系统数量算法

问题描述:

某国为了防御敌国的导弹袭击，开发了一种导弹拦截系统。该系统有一个缺陷：虽然第一发炮弹能够到达任意高度，但之后每一发炮弹的高度都不能高于前一发。已知敌方导弹来袭的高度，计算拦截所有导弹所需的最小系统数量。

算法思路:

定义一个数组存储导弹的高度。
找出最长的不上升子序列，即最多能拦截多少导弹。
将拦截导弹的数量与总导弹数量比较，得出所需系统数量。

代码实现:

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); // 输出所需系统数量
    }
}

代码解释:

height 数组存储输入的导弹高度。
dp 数组记录每个导弹位置能拦截的最大导弹数量。
循环遍历每个导弹，计算其能拦截的最大导弹数量，并将结果存储在 dp 数组中。
max 变量记录最长不上升子序列的长度，即最多能拦截的导弹数量。
最后输出 max 和 count - max，分别代表最大拦截数量和所需系统数量。

总结:

通过最长不上升子序列算法，我们成功地计算出拦截所有导弹所需的最小系统数量。该算法简单易懂，代码简洁高效，可以有效地解决导弹拦截问题。