计科院19孙博

用户名：uq_94474674840

访问量：691

签　名：

等　　级
排　　名	13382
经　　验	931
参赛次数	0
文章发表	5
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

枚举石头剪刀布
浏览：138

1209: 密码截获 java
浏览：122

你可能喜欢

拦截导弹(java) --最长上升子序列

　　作者: 计科院19孙博　　　　发表时间：2021-10-02 12:08:34 浏览：151　|　评论：1　

原题链接：信息学奥赛一本通T1260-拦截导弹

最长上升子序:是指一个序列中最长的单调递增的子序列,不是必须要连续.

#### **思路:**
**最长上升子序** :核心的解题思想就是从前到后扫描数组，并在对每一个元素扫描时，利用动态规划思想确定到当前下标位置的最长上升子序列。这里需要注意的是因为上升子序列不是必须要连续，所以递归式可以理解为 dp[i] = Math.max(dp[i], dp[j]+1)

**最长不上升子序:** 与最长上升子序一样 ,只是判断条件相反

#### **注意**：
- 求最多能拦截的导弹数就是求最长不上升子序
- 求拦截系统数，就是求最长上升子序
- 用最大上升子序列求最少的系统个数，因为上升序列是不可能在一个系统中拦截的，所以最大上升子序列的个数就是不可能在一个系统中的最大的个数，就是我们需要的系统的个数，dp的思想和前面是一样的。
#### 参考代码

```
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        while (scanner.hasNext()) {
            list.add(scanner.nextInt());
        }
        //记录数组中对应索引中它最长不上升子序个数
        int[] dp = new int[list.size()];
        //记录数组中对应索引中它最长上升子序个数
        int[] dp2 = new int[list.size()];

int maxLen = 0;
        int tigerNum = 0;
        Arrays.fill(dp,1); //填充
        Arrays.fill(dp2,1);
        //以list.get(i) 当作最长不上升子序中最小的元素 从数组第一个元素比较
        for (int i = 1; i < list.size(); i++) {
            for (int j = 0; j < i; j++) {
                if(list.get(i) <= list.get(j)){ //最长不上升子序
                    //动态规划思想
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }else {//最长上升子序
                    dp2[i] = Math.max(dp2[i],dp2[j]+1);
                }
            }
            maxLen = Math.max(maxLen,dp[i]);
            tigerNum = Math.max(tigerNum,dp2[i]);
        }
        System.out.println(maxLen);
        System.out.println(tigerNum);
    }

}

```

0.0分

2 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

计科院20级刘磊

学到了

2021-10-04 20:48:03

计科院19孙博

TA的其他文章

你可能喜欢

【作业调度方案】（C语言代码）

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

C语言考试练习题_保留字母（C语言代码）

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

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

拦截导弹(java) --最长上升子序列

评论区

精彩推荐

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

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

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

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

WU-判定字符位置（C++代码）

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

K-进制数（C语言描述，蓝桥杯）

Minesweeper （C语言描述，蓝桥杯）

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

关于float，double变量的几点说明

计科院19孙博

TA的其他文章

你可能喜欢

【作业调度方案】 （C语言代码）

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

C语言考试练习题_保留字母 （C语言代码）

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

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

拦截导弹(java) --最长上升子序列

评论区

精彩推荐

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

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

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

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

WU-判定字符位置 （C++代码）

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

K-进制数 （C语言描述，蓝桥杯）

Minesweeper （C语言描述，蓝桥杯）

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

关于float，double变量的几点说明

【作业调度方案】（C语言代码）

C语言考试练习题_保留字母（C语言代码）

　　评论区

WU-判定字符位置（C++代码）

K-进制数（C语言描述，蓝桥杯）