咖啡

用户名：Tianxn

访问量：129069

签　名：

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

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

　　自我简介：

TA的其他文章

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

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

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

你可能喜欢

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

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

　　作者: 咖啡　　　　发表时间：2019-06-14 14:03:33 浏览：1168　|　评论：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语言程序设计教程（第三版）课后习题4.9 （C语言代码）

【计算球体积】（C语言代码）

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

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

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

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

评论区

精彩推荐

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

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

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

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

简单的a+b （C语言代码）

用筛法求之N内的素数。（C++代码）

sizeof的大作用（C语言代码）

1035 题解

printf基础练习（C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

咖啡

TA的其他文章

你可能喜欢

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

【计算球体积】 （C语言代码）

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

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

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

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

评论区

精彩推荐

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

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

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

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

简单的a+b （C语言代码）

用筛法求之N内的素数。 （C++代码）

sizeof的大作用 （C语言代码）

1035 题解

printf基础练习 （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

【计算球体积】（C语言代码）

　　评论区

用筛法求之N内的素数。（C++代码）

sizeof的大作用（C语言代码）

printf基础练习（C语言代码）