学校网站需求,如何做购物网站的后台,二手房出售,python网站开发视频教程题目描述 看本文需要准备的知识
1.最长上升子序列#xff08;lis#xff09;的算法思想和算法模板
2.acwing1010拦截导弹#xff08;lis贪心#xff09;题解 本题题解#xff0c;需要知道这种贪心算法
3.简单了解dfs暴力搜索、剪枝、搜索树等概念
思路讲解
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(susdres)return;
意思是如果此次dfs的susd大于等于当前已经算出的需要最少的防御系统数量就直接把这个分支剪掉因为在这之后susd不可能比res小就不可能在这以下的分支获得更小的res
完整代码
#includeiostream
using namespace std;
const int N55;
int res;
int h[N],up[N],down[N];
int n;
void dfs(int u,int su,int sd)
{if(susdres)return;if(un){ressusd;return;}int k0;while(ksuup[k]h[u])k;if(ksu){int tup[k];up[k]h[u];dfs(u1,su,sd);up[k]t;}else{up[k]h[u];dfs(u1,su1,sd);}k0;while(ksddown[k]h[u])k;if(ksd){int tdown[k];down[k]h[u];dfs(u1,su,sd);down[k]t;}else{down[k]h[u];dfs(u1,su,sd1);}
}
int main()
{while(cinn,n){for(int i0;in;i)cinh[i];resn;dfs(0,0,0);coutresendl;}return 0;
}
