咖啡

用户名：Tianxn

访问量：138094

签　名：

十年OI一场空，不开LL见祖宗。

等　　级
排　　名	10
经　　验	27291
参赛次数	10
文章发表	197
年　　龄	22
在职情况	学生
学　　校	西安电子科技大学
专　　业	软件工程

　　自我简介：

TA的其他文章

信息学奥赛一本通T1309-回文数-题解（C++代码）
浏览：1324

信息学奥赛一本通T1255-迷宫问题-题解（C++代码）BFS求最短路
浏览：1104

信息学奥赛一本通T1255-迷宫问题-题解（C++代码）DFS求最短路
浏览：440

你可能喜欢

蓝桥杯算法训练VIP-拦截导弹-详细题解(C++语言代码) 动态规划最长不上升子序列和最长上升子序列（重新修正了一下思路~）

　　作者: 咖啡　　　　发表时间：2019-06-14 14:03:33 浏览：1389　|　评论：3　

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

1. 直接说了，最多能拦截的导弹的高度是不能超过上一次的高度，所以容易能想到最多能拦截的导弹数量就是所给序列的最长不上升子序列长度（并不是最长下降子序列）。而要拦截所有导弹需要的系统数目就是所给序列的最长上升子序列的长度（也就是把最长上升子序列中每一个数字分到不同的组里面即可），另外需要注意这个必须是最长上升子序列哈~。
	例如样例：389  207  155  300  299  170  158  65  111
	能拦截最多的导弹是6颗：389  300  299  170  158  65
	需要2台机器才能够拦截所有导弹：
		第一台：389 300 299 170 258 65
		第二台：207 155 111

2. 综上自己可以具体的画一画理解一下，下面具体说一下动态规划求最长上升子序列的求法：
	已知序列f[N];
	设dp[i]表示以f[i]结尾的最上上升子序列的长度，那么有如下状态转移方程：
		dp[i] = max{dp[i], dp[j] + 1}, 0 <= j < i且f[j] < f[i];
	根据上述推理过程两层for循环就可以求出最终结果。
	最长不上生子序列的求解方法和最长上升子序列的方法是相同的只需将条件中的 < 
	改为 >= 即可；状态转移方程如下：
		dp[i] = max{dp[i], dp[j] + 1}, 0 <= j < i且f[j] >= f[i];

3. 注意：dp过程中并不是最终结果就是最优值，需要再dp过程中记录最优值。

4. 代码如下：
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 3e4 + 9;
int dp1[N], dp2[N], f[N];
int main() {
	int idx = 0, ans = 0, cnt = 0;
	while(~scanf("%d", &f[idx])) idx++; // 遇到文件尾自动结束
	for(int i = 0; i < idx; ++i) {
		dp1[i] = dp2[i] = 1;
		for(int j = 0; j < i; ++j) {
			if(f[i] <= f[j]) { // 最长不上升子序列
				if(dp1[i] < dp1[j] + 1 ) dp1[i] = dp1[j] + 1;
			} else { // 最长上升子序列
				if(dp2[i] < dp2[j] + 1 ) dp2[i] = dp2[j] + 1;
			}
		}
		if(ans < dp1[i]) ans = dp1[i];
		if(cnt < dp2[i]) cnt = dp2[i];
	}
	printf("%d\n%d\n", ans, cnt);
	return 0;
}
```

如有错误，谢谢指出，纯手打…………

0.0分

15 人评分

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

　　评论区

输入哪有问题，你们真搞笑，循环输入到文件结束都不懂吗？

2020-04-26 10:31:47

KeyWolf

有问题啊 代码无限循环输入了

2019-12-08 14:49:43

17信网一班李岗

他这个题的输入是怎么回事，怎么知道有几个整数输入？

2019-10-09 16:25:32

咖啡

TA的其他文章

你可能喜欢

字符逆序（C语言代码）

人民币问题（C语言代码）

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

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

哥德巴赫曾猜测（C语言代码）

蓝桥杯算法训练VIP-拦截导弹-详细题解(C++语言代码) 动态规划最长不上升子序列和最长上升子序列（重新修正了一下思路~）

评论区

精彩推荐

星期判断机（C语言代码）

时间转换（C语言代码）

1162答案错误，为什么

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

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

C二级辅导-计负均正（C语言代码）

1199题解

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

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

计算质因子（Java代码）

咖啡

TA的其他文章

你可能喜欢

字符逆序 （C语言代码）

人民币问题 （C语言代码）

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

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

哥德巴赫曾猜测 （C语言代码）

蓝桥杯算法训练VIP-拦截导弹-详细题解(C++语言代码) 动态规划最长不上升子序列和最长上升子序列（重新修正了一下思路~）

评论区

精彩推荐

星期判断机 （C语言代码）

时间转换 （C语言代码）

1162答案错误，为什么

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

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

C二级辅导-计负均正 （C语言代码）

1199题解

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

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

计算质因子 （Java代码）

字符逆序（C语言代码）

人民币问题（C语言代码）

哥德巴赫曾猜测（C语言代码）

　　评论区

星期判断机（C语言代码）

时间转换（C语言代码）

C二级辅导-计负均正（C语言代码）

计算质因子（Java代码）