计科院20级刘磊

用户名：1579364808

访问量：4389

签　名：

写代码困了，就喝杯Java咖啡提提神

等　　级
排　　名	2497
经　　验	2278
参赛次数	6
文章发表	16
年　　龄	19
在职情况	学生
学　　校	怀化学院
专　　业	计算机科学与技术

　　自我简介：

计算机科学与技术专业的一名小码农

TA的其他文章

回溯法解决全排列
浏览：323

你可能喜欢

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

拦截导弹--(最长升序子序列)--动态规划

　　作者: 计科院20级刘磊　　　　发表时间：2021-10-04 23:55:12 浏览：382　|　评论：0　

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

###解题思路:
**子序列问题一般会想到动态规划和滑动窗口,关键在于是否一定连续,如果子序列一定连续那么一般就用滑动窗口,我一般喜欢称为子串,反之则一般用动态规划**
实际上这题就是经典动归题目[最长升序子序列](https://leetcode-cn.com/problems/longest-increasing-subsequence/ "最长升序子序列")的变体
- 求最多能拦截的导弹数实际上就是求最长不升序序列,我称之为"最长降序序列"
- 这题难点在于求要拦截所有导弹最少要配备的系统数,事实上只要求最长升序子序列就可以了,原因在于:**上升序列是不可能在一个系统中拦截的，所以最大上升子序列的个数就是不可能在一个系统中的最大的个数，就是我们需要的系统的个数**

####以最长升序子序列为例:
经典动归五部曲:
- **确定dp数组:dp[i] 表示以 nums[i] 这个数结尾的最长递增子序列的长度。**
- ** 确定状态转移方程:**
*假设我们已经知道了 dp[0..4] 的所有结果，我们如何通过这些已知结果推出 dp[5] 呢？*![](https://labuladong.gitee.io/algo/images/%E6%9C%80%E9%95%BF%E9%80%92%E5%A2%9E%E5%AD%90%E5%BA%8F%E5%88%97/3.jpeg)
**nums[5] = 3，既然是递增子序列，我们只要找到前面那些结尾比 3 小的子序列，然后把 3 接到最后，就可以形成一个新的递增子序列，而且这个新的子序列长度加一。**
显然，可能形成很多种新的子序列，但是我们只选择最长的那一个，把最长子序列的长度作为 dp[5] 的值即可
```java
for (int j = 0; j < i; j++) {
    if (nums[i] > nums[j]) 
        dp[i] = Math.max(dp[i], dp[j] + 1);
}
```
- 确定遍历顺序:确定遍历顺序
dp[i] 是有0到i-1各个位置的最长升序子序列 推导而来，那么遍历i一定是从前向后遍历。
- 确定 basecase: dp[i] 初始值为 1
- 举例验证打印dp数组

至此这题就做出来啦,最长降序子序列的求法也是类似的

###注意事项:
- 这题只是导弹高度不能高于之前,但是能相等  求最长降序子序列时判断条件为 if (nums[j]<=nums[i])

参考代码:
```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        ArrayList<Integer> list = new ArrayList<>();
        while(input.hasNextInt()){
            list.add(input.nextInt());
        }
        System.out.println(lengthOfLDS(list));
        System.out.println(lengthOfLIS(list));
    }
    public static int lengthOfLDS(List<Integer> list){
        int[] dp = new int[list.size()];//以nums[i]结尾的最长降序子序列
        Arrays.fill(dp,1);//base case:dp数组全部初始化为1
        int res =0;
        for (int i = 0; i < list.size(); i++) {
            for (int j = 0; j < i; j++) {
                if(list.get(j)>=list.get(i)){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;

}
    public static int lengthOfLIS(List<Integer> list){
        int[] dp = new int[list.size()];//以nums[i]结尾的最长升序子序列
        Arrays.fill(dp,1);//base case:dp数组全部初始化为1
        int res = 0;
        for (int i = 0; i < list.size(); i++) {
            for (int j = 0; j < i; j++) {
                if(list.get(j)<list.get(i)){
                    dp[i]=Math.max(dp[i],dp[j]+1);
                }
            }
            res = Math.max(res, dp[i]);
        }
        return res;
    }
}
```

0.0分

2 人评分

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

计科院20级刘磊

TA的其他文章

你可能喜欢

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

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

字符串的输入输出处理（C语言代码）

校门外的树（C++代码）

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

拦截导弹--(最长升序子序列)--动态规划

评论区

精彩推荐

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

C二级辅导-公约公倍（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

C语言训练-大、小写问题（C语言代码）

兰顿蚂蚁（C++代码）

WU-字符串比较（C++代码）

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

勾股数（C语言代码）

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

简单的事情（C语言代码）

计科院20级刘磊

TA的其他文章

你可能喜欢

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

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

字符串的输入输出处理 （C语言代码）

校门外的树 （C++代码）

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

拦截导弹--(最长升序子序列)--动态规划

评论区

精彩推荐

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

C二级辅导-公约公倍 （C语言代码）

C语言考试练习题_一元二次方程 （C语言代码）

C语言训练-大、小写问题 （C语言代码）

兰顿蚂蚁 （C++代码）

WU-字符串比较 （C++代码）

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

勾股数 （C语言代码）

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

简单的事情 （C语言代码）

字符串的输入输出处理（C语言代码）

校门外的树（C++代码）

　　评论区

C二级辅导-公约公倍（C语言代码）

C语言考试练习题_一元二次方程（C语言代码）

C语言训练-大、小写问题（C语言代码）

兰顿蚂蚁（C++代码）

WU-字符串比较（C++代码）

勾股数（C语言代码）

简单的事情（C语言代码）