防御导弹----------1287java

2022 年 04 月 29 日

277 次浏览

912字数

题目描述

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

输入描述

最多20个整数，分别表示导弹依次飞来的高度（雷达给出高度数据是不大于30000的正整数）

输出描述

整数M。表示：这套系统最多能拦截 M 枚导弹.

样例输入

300 250 275 252 200 138 245

样例输出

源代码：

import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
    //求最长不上升子序列的长度
       static int[] num = new int[100010];//用于存放数组
        static int[] dp = new int[100010];
        static int l;//用于存放输入值的长度
        public static void main(String[] args) throws Exception{
            //为了获得最佳效率将BufferedReader和InputSreamReader结合使用
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] str = br.readLine().split(" ");//输入数据
            l = str.length;//字符串的长度
            for(int i=1;i<=l;i++){//第一个循环将数据存放入数组
                num[i] = Integer.parseInt(str[i-1]);//将字符转化为int类型存入num数组中
                dp[i]=1;//将每个dp都赋值为1
            }
            for(int i=1;i<=l;i++){//双层循环进行对比
                for(int j=1;j<i;j++){
                    if(num[i]<=num[j]&&dp[i]<dp[j]+1){
                        dp[i]=dp[j]+1;
                    }
                }
            }
            int max = -1;
            for(int i=1;i<=l;i++){
                if(dp[i]>max){
                    max = dp[i];
                }
            }
            System.out.println(max); 
        }
}

小结：

本题为动态规划问题。
本题的分析：
本题本质上就是求不上升子序列的最大长度
1、设立一个数组num用于存放各组数的值
2、将每个dp数组的值设为1.为初始值，用于判断最后的最大长度
3、以题目中的样例输入为例：

（当i==1时其他情况不成立判断条件，省略）
当i==2&&j==1时
250<=300  dp[2]=dp[1]+1=2
（dp[2]赋值完毕）
当i==3&&j==1时
275<=300  dp[3]=dp[1]+1=2
（dp[3]赋值完毕）
当i==4&&j==1时
252<=300  dp[4]=dp[1]+1=2
当i==4&&j==3时
252<=275  dp[4]=dp[3]+1=3
（dp[4]赋值完毕）
当i==5&&j==1时
200<=300  dp[5]=dp[1]+1=2
当i==5&&j==2时
200<=250  dp[5]=dp[2]+1=3
当i==5&&j==3时
200<=275  dp[5]=dp[3]+1=3
当i==5&&j==4时
200<=252  dp[5]=dp[4]+1=4
（dp[5]赋值完毕）
当i==6&&j==1时
138<=300  dp[6]=dp[1]+1=2
当i==6&&j==2时
138<=250  dp[6]=dp[2]+1=3
当i==6&&j==4时
138<=252  dp[6]=dp[4]+1=4
当i==6&&j==5时
138<=200  dp[6]=dp[5]+1=5
（dp[6]赋值完毕）
当i==7&&j==1时
245<=300  dp[7]=dp[1]+1=2
当i==7&&j==2时
245<=250  dp[7]=dp[2]+1=3
当i==7&&j==4时
245<=252  dp[7]=dp[4]+1=4
（dp[7]赋值完毕）

最后在循环条件下得出最优解即dp[6]=5

防御导弹----------1287java