除去升序序列后，再求降序，当升序过后，降序就是需几套系统，详细看题解

420 阅读 0 评论 0 点赞

这个题要先学会**动态规划求上升子序列**
为什么我说除去降序子序列过后，再找出升序就是它需要几套系统：
首先我们通过题目知道:**但是以后每一发炮弹都不能高于前一发的高度**
是要求一个降序的，也就是**arr[0]>arr[1]**,所以我们就先使用**动态规划求下降子序列**，和上升上一个道理。
所以过程就是：
389 207 155 300 299 170 158 65
| 1 || 2 | | 3 | | 2 | | 3 | | 4 | | 5 | | **6** |当前元素结尾的最长下降子元素
也就是：389 300 299 170 158 65|六个
推导公式为：
0+1：是本身的长度
f(0)=0+1;
f(1)=max(f(0)+1,0+1)
f(2)=max(f(0)+1,f1(1)+1，0+1)
........
1、定义dp[0——n]的意义：dp[i]为以当前arr[i]**结尾**最长下降子序列的长度。
2、在题目中，我们知道，一定是**当前**元素，要小于**前面**的元素，才能使用，也就是：arr[j] > arr[i] (389 300)
3、既让要找到最大值，就要遍历我前面的所有元素:
for : dp[i]=max (dp[j]+1,dp[i]) 就是(f(2)=f(1)+1,0+1 )......

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String nextLine = sc.nextLine();
		String[] split = nextLine.split(" ");
		int[] arr = new int[split.length];
		int[] dp = new int[split.length];
		int[] dp1 = new int[split.length];
		for (int i = 0; i < dp.length; i++) {
			arr[i] = Integer.parseInt(split[i]);
			dp[i] = 1;
			dp1[i] = 1;
		}
		// dp[i]是以arr[i]结尾的最长下降子序列
		int max1 = 0;
		for (int i = 0; i < dp.length; i++) {
			// arr[0——arr[i]结尾]所有元素
			for (int j = 0; j < i; j++) {
				if (arr[i] <= arr[j]) {
					dp[i] = Math.max(dp[i], dp[j] + 1);
				}
			}
			max1 = Math.max(dp[i], max1);
		}
		System.out.println(max1);
		
	}
	
	
这样就找到了最长下降子序列，
这个时候就该想，使用最小套数怎么弄了：
仔细看，389 207 155 300 299 170 158 65
要想吧全部数据都遍历完，也就是除去**最长下降子序列**其他元素，既让是剩下的元素，就是**最长下降子序列，**的相反，**最长上升序列**。

```java
int max2 = 0;
		for (int i = 0; i < dp1.length; i++) {
			for (int j = 0; j < i; j++) {
				if (arr[i] > arr[j]) {
					dp1[i] = Math.max(dp1[i], dp1[j] + 1);
				}
			}
			max2 = Math.max(max2, dp1[i]);
		}
		System.out.println(max2);
```
ok————————故得白！

0.0分

2 人评分

本文分类：题解列表
浏览次数：420 次浏览
发布日期：2023-03-16 14:21:37
本文链接：https://blog.dotcpp.com/a/94921

上一篇 > 超级简单，来理解一下吧
下一篇 > 矩阵快速幂-python（最后一个运行超时）

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

除去升序序列后，再求降序，当升序过后，降序就是需几套系统，详细看题解

评论列表共有 0 条评论

发表评论取消回复

除去升序序列后，再求降序，当升序过后，降序就是需几套系统，详细看题解

一笔画问题（dfs）

C++ ： 类和两种访问权限的练习

C++ ： 类和两种访问权限的练习

幸运儿（约瑟夫环-模拟+ Vector）

评论列表 共有 0 条评论

发表评论 取消回复

C++ ：类和两种访问权限的练习

C++ ：类和两种访问权限的练习

评论列表共有 0 条评论

发表评论取消回复