【Acwing187】导弹防御系统（LIS+剪枝+贪心+dfs+迭代加深）

题目描述

看本文需要准备的知识

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的开头也可以做一个小剪枝：

if(su+sd>=res)return;

意思是：如果此次dfs的su+sd大于等于当前已经算出的需要最少的防御系统数量，就直接把这个分支剪掉，因为在这之后su+sd不可能比res小，就不可能在这以下的分支获得更小的res

完整代码

#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;
}