瞿肖

用户名：uq_33500452490

访问量：1676

签　名：

等　　级
排　　名	4520
经　　验	1679
参赛次数	1
文章发表	14
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

全天下的温柔共十分，你占八分，遇见你那晚的凉风秋月占一分，你说你也喜欢我的那刻占一分。

TA的其他文章

三维数组存储地图，广度搜索最短路径
浏览：95

广搜的节点存放起始地，最后递归输出节点（链表）
浏览：34

和八皇后很类似，不过八皇后的想法更简单（判断合法性繁琐），这个题多了一个有：可能这一行不放棋子
浏览：216

你可能喜欢

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

　　作者: 瞿肖　　　　发表时间：2023-03-16 14:21:37 浏览：221　|　评论：0　

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

这个题要先学会**动态规划求上升子序列**
为什么我说除去降序子序列过后，再找出升序就是它需要几套系统：
首先我们通过题目知道:**但是以后每一发炮弹都不能高于前一发的高度**
是要求一个降序的，也就是**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分

3 人评分

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

瞿肖

TA的其他文章

你可能喜欢

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

人见人爱A+B （C++代码）

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

C二级辅导-同因查找（C语言代码）

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

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

评论区

精彩推荐

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

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

WU-拆分位数（C++代码）

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

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

蛇行矩阵（C语言代码）

IP判断（C语言描述，蓝桥杯）

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

图形输出（C语言代码）

输入输出格式练习（C语言代码）

瞿肖

TA的其他文章

你可能喜欢

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

人见人爱A+B （C++代码）

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

C二级辅导-同因查找 （C语言代码）

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

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

评论区

精彩推荐

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

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

WU-拆分位数 （C++代码）

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

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

蛇行矩阵 （C语言代码）

IP判断 （C语言描述，蓝桥杯）

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

图形输出 （C语言代码）

输入输出格式练习 （C语言代码）

C二级辅导-同因查找（C语言代码）

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

　　评论区

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

WU-拆分位数（C++代码）

蛇行矩阵（C语言代码）

IP判断（C语言描述，蓝桥杯）

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

图形输出（C语言代码）

输入输出格式练习（C语言代码）