题目描述
看本文需要准备的知识
1.最长上升子序列（lis）的算法思想和算法模板
2.acwing1010拦截导弹（lis+贪心）题解 本题题解，需要知道这种贪心算法
3.简单了解dfs暴力搜索、剪枝、搜索树等概念
思路讲解
dfs求最小步数有两种方法：记一个全局最小值，迭代加深
bfs的缺点：空间太大、不好剪枝
此处采用dfs的迭代加深
首先，这道题的爆搜思路为：从前往后枚举每颗导弹属于某个上升子序列，还是下降子序列；
如果属于上升子序列，则枚举属于哪个上升子序列（包括新开一个上升子序列）；如果属于下降子序列，可以类似处理
那么搜索树就会十分的大，如下所示：
如何剪枝，首先可以采用acwing1010的贪心策略（下面放题解链接），这样就不用遍历插入每一个序列的分支了，而是在上升时（包含插入已有上升序列和新增一个上升序列）或者下降时（包含插入已有下降序列和新增一个下降序列）就确定了要选择哪种分支，而把其它分支全部剪掉！
acwing1010拦截导弹（lis+贪心）题解
优化之后，搜索树就简化为：
dfs的函数原型设为：
dfs(u,su,sd):
其中u代表现在遍历的序列第几个数，su表示现在上升序列的个数，sd表示现在下降序列的个数
答案res初始化为n（因为最多需要的防御系统的个数就是n）
在dfs的开头也可以做一个小剪枝：文章来源：https://www.toymoban.com/news/detail-726488.html
if(su+sd>=res)return;意思是：如果此次dfs的su+sd大于等于当前已经算出的需要最少的防御系统数量，就直接把这个分支剪掉，因为在这之后su+sd不可能比res小，就不可能在这以下的分支获得更小的res文章来源地址https://www.toymoban.com/news/detail-726488.html
完整代码
#include<iostream>
using namespace std;
const int N=55;
int res;
int h[N],up[N],down[N];
int n;
void dfs(int u,int su,int sd)
{
if(su+sd>=res)return;
if(u==n)
{
res=su+sd;
return;
}
int k=0;
while(k<su&&up[k]>h[u])k++;
if(k<su)
{
int t=up[k];
up[k]=h[u];
dfs(u+1,su,sd);
up[k]=t;
}
else
{
up[k]=h[u];
dfs(u+1,su+1,sd);
}
k=0;
while(k<sd&&down[k]<h[u])k++;
if(k<sd)
{
int t=down[k];
down[k]=h[u];
dfs(u+1,su,sd);
down[k]=t;
}
else
{
down[k]=h[u];
dfs(u+1,su,sd+1);
}
}
int main()
{
while(cin>>n,n)
{
for(int i=0;i<n;i++)cin>>h[i];
res=n;
dfs(0,0,0);
cout<<res<<endl;
}
return 0;
}到了这里，关于【Acwing187】导弹防御系统（LIS+剪枝+贪心+dfs+迭代加深）的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
