敖屹

用户名：uq_67615411132

访问量：767

签　名：

啥都学，但是啥都学不会

等　　级
排　　名	2598
经　　验	2245
参赛次数	7
文章发表	2
年　　龄	19
在职情况	学生
学　　校	长江大学文理学院
专　　业	计算机应用技术

　　自我简介：

一个喜欢数学和计算机的小菜鸡

TA的其他文章

拦截导弹(C++和Java)(动态规划模板：最长上升子序列)
浏览：408

你可能喜欢

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

拦截导弹(C++和Java)(动态规划模板：最长上升子序列)

　　作者: 敖屹　　　　发表时间：2023-11-22 23:54:39 浏览：408　|　评论：1　

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

#拦截导弹(C++和Java)(动态规划模板：最长上升子序列)
##将题意转化一下
先理解题目，理解之后可以转化为两个题目：
**问题1：**给定一个数组，求最长不上升子序列的长度
**问题2：**给定一个数组，最少有多少个最长不上升子序列可以完全包含这个数组中的每一个值
##接下来我们分开来讨论这两个问题
###问题1：给定一个数组，求最长不上升子序列的长度
求解最长上升子序列这类问题（也称为LIS）一般有三种解法：
1.线性dp（时间复杂度：$$O(N^2)$$）
2.二分+单调栈（时间复杂度：$$O(NlogN)$$）
3.树状数组（index树）或者线段树（时间复杂度：$$O(NlogN)$$）
**由于此题的数据量比较小，所以这里只说简单的方法：线性dp，其他方法读者可以自行去了解**
####线性dp解法：
**dp数组的设计：** $$dp[i]$$是以$$i$$位置上的数做结尾的最长不上升子序列
**实现思路：**假设$$j$$是$$i$$之前的某一位置，那么很明显可以看出如果$$arr[i]<=arr[j]$$,则有$$dp[i]=max(dp[j]+1)$$
说人话就是$$dp[i]$$的值等于在$$i$$位置之前的最长不上升子序列的长度+1
那么很容易就可以得出状态转移方程如下
$$dp[i]=max(dp[i],dp[j]+1),其中j<i,且arr[i]<=arr[j]$$
**所以直接上伪代码**
```
//这里的arr数组的下标是从1开始的
for (int i = 1; i <= n; i++) {
	for (int j = 1; j < i; j++) {
		if (arr[i] <= arr[j])
			dp[i] = max(dp[i], dp[j] + 1);
		maxx = max(maxx, dp[i]);
	}
}
//maxx就是最终的结果了
```
###问题2：给定一个数组，最少有多少个最长不上升子序列可以完全包含这个数组中的每一个值
####引理：
**Dilworth定理:**偏序集的最少反链划分数等于最长链的长度
**根据如上定理可知：**把数组划分成最少的不上升子序列个数等于这个数组的最长上升子序列的长度
####解法
那么本质上就是求数组的最长上升子序列,上面已经说了怎么求最长不上升子序列,那么同理,最长上升子序列的求法几乎一样(只要让dp数组的含义变一下，然后同理那样推就可以了),下面直接上伪代码了
```
//这里的arr数组的下标是从1开始的
for (int i = 1; i <= n; i++) {
	for (int j = 1; j < i; j++) {
		if (arr[i] > arr[j])
			dp[i] = max(dp[i], dp[j] + 1);
		maxx = max(maxx, dp[i]);
	}
}
//maxx就是最终的结果了
```
##将两个问题合并一下
最长上升子序列和最长不上升子序列可以一起求，合一起就是如下伪代码
```
//这里的arr数组的下标是从1开始的
for (int i = 1; i <= n; i++) {
    for (int j = 1; j < i; j++) {
		//最长上升子序列
        if (arr[i] > arr[j])
            dp1[i] = max(dp1[i], dp1[j] + 1);
		//最长不上升子序列
		if (arr[i] <= arr[j])
            dp2[i] = max(dp2[i], dp2[j] + 1);
		max1 = max(max1, dp1[i]);
		max2 = max(max2, dp2[i]);
    }
}
//max1就是最长上升子序列的长度
//max2就是最长不上升子序列的长度
```
##具体代码实现(C++的实现)(Java的实现在后面)
```cpp
#include <iostream>
#define N 1008

using namespace std;

int arr[N];
int dpDecrease[N];
int dpIncrease[N];

int main() {
	int maxx = -1;
	int ans = -1;
	int tt = 1;
	while (cin >> arr[tt]) {
		dpDecrease[tt] = 1;
		dpIncrease[tt++] = 1;
	}
	for (int i = 1; i < tt; i++) {
		for (int j = 1; j < i; j++) {
			if (arr[i] <= arr[j])
				dpDecrease[i] = max(dpDecrease[i], dpDecrease[j] + 1);
			if (arr[i] > arr[j])
				dpIncrease[i] = max(dpIncrease[i], dpIncrease[j] + 1);
		}
		maxx = max(maxx, dpDecrease[i]);
		ans = max(ans, dpIncrease[i]);
	}
	cout << maxx << "\n" << ans << endl;
	return 0;
}
```
##具体代码实现(Java的实现)
```Java
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String input = scanner.nextLine();
        String[] strs = input.split(" ");
        int[] arr = new int[strs.length];
        int[] dpDecrease = new int[strs.length];
        int[] dpIncrease = new int[strs.length];
        int maxx = -1,ans = -1;
        for (int i = 0; i < strs.length; i++){
            arr[i] = Integer.parseInt(strs[i]);
            dpDecrease[i] = 1;
            dpIncrease[i] = 1;
        }
        for(int i = 0;i < arr.length;i++){
            for(int j = 0;j < i;j++){
                if (arr[i] <= arr[j])
                    dpDecrease[i] = Math.max(dpDecrease[i], dpDecrease[j] + 1);
                if (arr[i] > arr[j]) 
                    dpIncrease[i] = Math.max(dpIncrease[i], dpIncrease[j] + 1);
            }
            maxx = Math.max(maxx, dpDecrease[i]);
            ans = Math.max(ans, dpIncrease[i]);
        }

System.out.println(maxx);
        System.out.println(ans);
        scanner.close();
    }
}
```

0.0分

11 人评分

新上线《蓝桥杯辅导》课程，近五年的蓝桥杯省赛与国赛真题都有，从读题开始理解题意、梳理思路、实现代码再提交评测全过程，可有效提升获奖比例甚至进国赛！课程介绍、试听请猛击这里

　　评论区

博博想去大厂啊

6666666666666666666666666666

2024-04-08 09:53:33

敖屹

TA的其他文章

你可能喜欢

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

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

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

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

不知道哪里错了

拦截导弹(C++和Java)(动态规划模板：最长上升子序列)

评论区

精彩推荐

P1002 （C语言代码）

【绝对值排序】（C++代码）

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

兰顿蚂蚁（C++代码）

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

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

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

1048题解（读入回车问题）

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

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

敖屹

TA的其他文章

你可能喜欢

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

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

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

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

不知道哪里错了

拦截导弹(C++和Java)(动态规划模板：最长上升子序列)

评论区

精彩推荐

P1002 （C语言代码）

【绝对值排序】 （C++代码）

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

兰顿蚂蚁 （C++代码）

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

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

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

1048题解（读入回车问题）

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

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

　　评论区

【绝对值排序】（C++代码）

兰顿蚂蚁（C++代码）