Glimmer

**先讲贪心，本题贪心算法的关键在于，若存在多个可拦截当前导弹的系统，需选择其中高度最小的，也就是使每个系统最后都成为一个最长不上升子序列**
```cpp
#include<iostream>
using namespace std;
int n;
int h[1005];//记录导弹高度
int s[1005];//记录每个系统当前可拦截最高高度
int main()
{
	while (cin >> h[n])
		n++;
	int cnt = 1;//记录系统数
	s[cnt] = h[0];//初始化，把第一个导弹高度录入第一个系统
	for (int i = 1; i < n; i++)//遍历导弹
	{
		int p = 0;//初始化！！！
		for (int j = 1; j <= cnt; j++)//遍历当前已有系统
		{
			if (s[j] >= h[i])//如果第j个系统最大高度大于当前导弹
			{
				if (p == 0)
					p = j;//若p==0，即第一次从已有系统中找到可用系统，则记录当前系统编号
				else if (s[p] > s[j])//若存在有比已记录系统更优选择，则记录更优者。注意！！！重点，贪心思想！！！
					p = j;
			}
		}
		if (!p)//若p==0，即不存在可拦截系统
		{
			s[++cnt] = h[i];//新建一个，且更新其可拦截最大高度
		}
		else
			s[p] = h[i];//更新可拦截最大高度
	}
	cout << cnt;//输出系统数
	return 0;
}
```
**再来讲动态规划，从动态规划的角度来看，本题是一个典型的序列型动态规划问题，我们可以留意最优解下每个拦截系统最开始拦截的高度，这是一个上升序列，那么在最优解下这就是一个最长上升子序列**
那问题就简单了，求最长上升子序列，代码如下：
```cpp
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int h[1005];
int dp[1005];
int n;
int res;
int main()
{
	while (cin>>h[n])
		n++;
	fill(dp, dp + 1005, 1);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (h[i] > h[j])
				dp[i] = max(dp[i], dp[j] + 1);
		}
		res = max(res, dp[i]);
	}
	cout << res;
	return 0;
}
```

0.0分

13 人评分

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

　　评论区

22308包封波

感谢，已经懂了

2024-03-20 11:14:12

息月

太牛啦

2022-03-29 21:38:00

Glimmer

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C++代码）

弟弟的作业（C++代码）

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

时间转换（Java代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）（经常这样写会不会被打死）

拦截导弹问题贪心和动态规划两种方法，详细注释

评论区

精彩推荐

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

C语言训练-求函数值（C语言代码）

母牛的故事（C语言代码）

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

A+B for Input-Output Practice (IV) （C语言代码）

字符逆序（C语言代码）

【出圈】（C++代码）简单循环

三角形（C语言代码）

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

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

Glimmer

TA的其他文章

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(2) （C++代码）

弟弟的作业 （C++代码）

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

时间转换 （Java代码）

C语言程序设计教程（第三版）课后习题6.7 （C++代码）（经常这样写会不会被打死）

拦截导弹问题 贪心和动态规划两种方法，详细注释

评论区

精彩推荐

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

C语言训练-求函数值 （C语言代码）

母牛的故事 （C语言代码）

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

A+B for Input-Output Practice (IV) （C语言代码）

字符逆序 （C语言代码）

【出圈】 （C++代码）简单循环

三角形 （C语言代码）

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

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

弟弟的作业（C++代码）

时间转换（Java代码）

拦截导弹问题贪心和动态规划两种方法，详细注释

　　评论区

C语言训练-求函数值（C语言代码）

母牛的故事（C语言代码）

字符逆序（C语言代码）

【出圈】（C++代码）简单循环

三角形（C语言代码）