陈正磊

用户名：RossTran

访问量：13671

签　名：

晨兴理荒秽，带月荷锄归。

等　　级
排　　名	178
经　　验	6683
参赛次数	15
文章发表	34
年　　龄	0
在职情况	学生
学　　校	湖北生物科技职业学院
专　　业

　　自我简介：

TA的其他文章

蓝桥杯算法训练VIP-字符串的展开-题解（Java代码）
浏览：279

简单的字符串-题解（Java代码）
浏览：227

绝对值排序-题解（Java代码）
浏览：262

你可能喜欢

蓝桥杯算法训练VIP-拦截导弹-题解(Java代码)

　　作者: 陈正磊　　　　发表时间：2020-02-22 20:57:10 浏览：1151　|　评论：4　

原题链接：蓝桥杯算法训练VIP-拦截导弹

这题乍一看有点唬人，但画个图一看是求**最长不上升序列**和**最长不下降序列**。
您请看图--
导弹从上往下拦截的，每次只能拦截比上一个高度小或者相等高度的导弹；
序列可以是不连续的，串是连续的
![](/image_editor_upload/20200222081353_85218.jpg)
*导弹按顺序飞来的高度

------------

![](/image_editor_upload/20200222081553_67823.jpg)
*这是图中最长的不上升线路图，一共六个点，即这套系统最多能拦截六颗导弹

------------

![](/image_editor_upload/20200222081913_11772.jpg)
*这是图中最长的不下降线路图，一共两个点，即最少需要两套拦截系统，可能这图看起来不直观，修改一下数据看下图

------------
![](/image_editor_upload/20200222084345_75483.jpg)
*同一颗炮弹必不可能拦截最长不下降点处的多个导弹，所以最少需要如图所示节点个数的拦截炮弹。
     
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Scanner;
     
    public class Main {     
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            
            //将输入的内容添加到list
            List<Integer> list=new ArrayList<Integer>();//存储数组内容
            Scanner ss=new Scanner(sc.nextLine());//输入换行结束
            while (ss.hasNext()) {
            	int x=ss.nextInt();
    			list.add(x);
    		}
            int []dp=new int[list.size()];//动态规划表格
            
            //最长不上升序列问题  (最多能拦截导弹数)
            int maxVal=0;
            for (int i = 0; i <list.size(); i++) {
            	dp[i]=1;
    			for (int j = 0; j <i; j++) {
    				if (list.get(i)<=list.get(j)&&dp[i]<(dp[j]+1)) {
    					dp[i]=dp[j]+1;
    				}
    			}
    			if (maxVal<dp[i]) {
    				maxVal=dp[i];
    			}
    		}
            
          //最长不下降序列问题  (使用最少套导弹数)
            int minVal=0;
            for (int i = 0; i <list.size(); i++) {
            	dp[i]=1;
    			for (int j = 0; j <i; j++) {
    				if (list.get(i)>list.get(j)&&dp[i]<(dp[j]+1)) {
    					dp[i]=dp[j]+1;
    				}
    			}
    			if (minVal<dp[i]) {
    				minVal=dp[i];
    			}
    		}
            
            System.out.println(maxVal);
            System.out.println(minVal);
        }
    }

0.0分

16 人评分

看不懂代码？想转换其他语言的代码？或者想问其他问题？试试问问AI编程助手，随时响应你的问题：

　　评论区

来自澳大利亚的兵

醍醐灌顶

2023-04-05 20:44:13

月初

幸好你是java组的

2022-02-08 20:32:31

陈强

就服你

2021-04-07 10:39:33

万天明

牛逼

2020-03-22 18:13:04

陈正磊

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

字符逆序（C语言代码）

汽水瓶（C++代码）

The 3n + 1 problem （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

蓝桥杯算法训练VIP-拦截导弹-题解(Java代码)

评论区

精彩推荐

A+B for Input-Output Practice (VI) （C语言代码）

十->二进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

字符串对比（C语言代码）

输出正反三角形（C语言代码）

陈正磊

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题9.4 （C语言代码）

字符逆序 （C语言代码）

汽水瓶 （C++代码）

The 3n + 1 problem （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C++代码）

蓝桥杯算法训练VIP-拦截导弹-题解(Java代码)

评论区

精彩推荐

A+B for Input-Output Practice (VI) （C语言代码）

十->二进制转换 （C语言代码）

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码） 用函数传参的方法

简单的a+b （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

A+B for Input-Output Practice (IV) （C++代码）

字符串对比 （C语言代码）

输出正反三角形 （C语言代码）

字符逆序（C语言代码）

汽水瓶（C++代码）

　　评论区

十->二进制转换（C语言代码）

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）用函数传参的方法

字符串对比（C语言代码）

输出正反三角形（C语言代码）