敖屹

用户名：uq_67615411132

访问量：351

签　名：

啥都学，但是啥都学不会

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

　　自我简介：

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

TA的其他文章

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

你可能喜欢

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

　　作者: 敖屹　　　　发表时间：2023-11-22 23:54:39 浏览：152　|　评论：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分

4 人评分

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

编程语言转换

万能编程问答

代码解释器

　　评论区

博博想去大厂啊

6666666666666666666666666666

2024-04-08 09:53:33

敖屹

TA的其他文章

你可能喜欢

拆分位数（C语言代码）

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

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

众数问题（C语言代码）

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

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

评论区

精彩推荐

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

【出圈】（C语言代码）

WU-printf基础练习2 （C++代码）

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

求圆的面积（C语言代码）

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

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

C二级辅导-阶乘数列（C语言代码）

Hello, world! （C语言代码）

勾股数（C语言代码）

敖屹

TA的其他文章

你可能喜欢

拆分位数 （C语言代码）

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

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

众数问题 （C语言代码）

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

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

评论区

精彩推荐

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

【出圈】 （C语言代码）

WU-printf基础练习2 （C++代码）

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

求圆的面积 （C语言代码）

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

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

C二级辅导-阶乘数列 （C语言代码）

Hello, world! （C语言代码）

勾股数 （C语言代码）

拆分位数（C语言代码）

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

众数问题（C语言代码）

　　评论区

【出圈】（C语言代码）

求圆的面积（C语言代码）

C二级辅导-阶乘数列（C语言代码）

勾股数（C语言代码）