导弹防御系统(贪心，dfs)

目录

题目

思路：

代码

题目

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。

一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。

例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。 

给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

输入格式
输入包含多组测试用例。

对于每个测试用例，第一行包含整数 n，表示来袭导弹数量。

第二行包含 n 个不同的整数，表示每个导弹的高度。

当输入测试用例 n=0 时，表示输入终止，且该用例无需处理。

输出格式
对于每个测试用例，输出一个占据一行的整数，表示所需的防御系统数量。

数据范围
1≤n≤50

输入样例：
5
3 5 2 4 1
0

输出样例：
2

本题可以用贪心+迭代加深（迭代加深暂时不会，等我会了的时候再写）

思路：

依次枚举每个数

先枚举将该数放到单挑上升的序列中，还是单调下降的序列中

1、如果该数被放到了单调上升的序列中，则枚举将该数放到哪个单调上升的序列后面（优化 放到小于该数的最大的数后面）

2、如果该数被放到了单调下降的序列中，则枚举将该数放到哪个单调下降的序列后面（优化 放到大于该数的最大的数后面）

优化  up[]存储当前所有上升子序列的末尾元素，down[]存储当前所有下降子序列的末尾元素

用up[k]和down[k]记录第k套上升（下降）系统目前所拦截的最后一个导弹
dfs(u,v,t)意味着已有u个上升，v个下降，正在处理第t个数

按理说，每拿到一个新的数字应该将它所有能放入的序列都放一遍的
但扩展节点时却存在一个贪心策略，大大节省了时间。
假设现在要把一个数放入一个上升序列，那么一定是所有能放入的上升序列中，最后一个元素最大的那一个。
其实想想也是，既然每个数字都要放到一个序列中，
对于上升序列，肯定是目前越小越有用，既然能放入大的里面，何必浪费一个小的呢
注意到其实up[i]按这种策略已经是排好序的了，所以只用找最先碰到的一个就行了
 

代码

#include
#include
using namespace std;
const int N=60;
int n,ans;
int a[N],up[N],down[N];
//u表示有几个单调上升的子序列，d表示有几个单调下降的子序列，t表示正在处理t个数
void dfs(int u,int d,int t)
{if(u+d>=ans) return ;//如果大于当前的最优解 返回上一层if(t==n)//数全部便利完{if(u+dup[i]) break;//存起来，方便恢复现场int temp=up[i];up[i]=a[t];//更改此up[i]中最后一个元素的值
//对于max 有可能找不到一个比a[t]小的数 就需要从新在开一个up[],此时的i=u+1;dfs(max(u,i),d,t+1);up[i]=temp;//恢复现场for(i=1;i<=d;i++)
//找到第一个大于a[t]的值（down[i]小到大）if(a[t]>n){if(n==0) break;for(int i=0;i>a[i];ans=110;dfs(0,0,0);cout<

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！