瞿肖

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

C语言网提供「C语言、C++、算法竞赛、真题百练、Python课程」在线课程，全部由资深研发工程师或ACM金牌大佬亲授课，更科学、全面的课程体系，以在线视频+在线评测的学习模式学习，学练同步，拒绝理论派，真正学会编程！还有奖学金等增值福利等你！

瞿肖

TA的其他文章

你可能喜欢

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

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

【出圈】（C语言代码）用单项循环链表

【蟠桃记】（C语言代码）

C二级辅导-进制转换（C语言代码）

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

评论区

精彩推荐

2^k进制数（C++代码）使用递归方法

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

Hello, world! （C语言代码）

【排队买票】（C语言代码）

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

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

1009题解

回文数字（C语言代码）

愚蠢的摄影师（C++代码）

1013题解

瞿肖