POJ - 3700 Missile Defence System.(dfs+最优性剪枝)

题目链接：点击查看

题目大意：给出n个导弹的飞行高度，规定一个导弹拦截装置只能拦截严格升序的导弹或严格降序的导弹，问拦截所有导弹需要最少多少个拦截装置

题目分析：之前做过一个dp题，那个题目简单，是只有拦截严格降序的导弹，这个题目就不能再用dp的思想了，我们其实可以考虑用搜索，将其转化为一棵平衡二叉树来想，每到达一个导弹我们都有四种选择：

用之前升序的拦截系统拦截

新建一个升序的拦截系统

用之前降序的拦截系统拦截

新建一个降序的拦截系统

很显然，我们秉承着能省则省的原则，可以查找之前用过的拦截系统能否拦截当前导弹，若可以拦截，则无需新建，否则就需要新建一个，这样我们每一层的选择就由四个变成了两个，每次都要从1/2和3/4中选出两个进行递归遍历，形成一个平衡二叉树。

如果每次都遍历到叶子结点的话，时间复杂度未免也太大了，所以我们需要增加一个最优性剪枝，若当前的答案已经大于等于当前的最优解了，我们就可以直接回溯，在初始化时我们将答案初始化为n即可，因为最差也就是每个导弹都需要单独的一个拦截系统，这样就可以顺利AC了，代码写的有点乱，不过思路清晰，我尽量加点注释解释一下

对了，这个题目还有点贪心的成分，比如前面已经有cnt1个升序拦截系统了，现在导弹的高度设为h，那么我们如果想用前面的拦截系统来拦截该导弹，我们肯定会选择高度比h低的拦截系统中的最大值，这个很好想，但我不会证明，就当做显然条件吧

代码：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<sstream> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=55;int n,ans,cnt1,cnt2;//ans：答案 cnt1：上升拦截系统用了多少个 cnt2：下降拦截系统用了多少个int a[N];//每个导弹高度int up[N],down[N];//up：上升拦截系统 down：下降拦截系统void dfs(int cnt) {if(cnt1+cnt2>=ans)//最优性剪枝return; if(cnt==n+1)//若所有导弹都已分配完毕，更新答案{ans=cnt1+cnt2;return;}int mark=-1;//用来记录最大值/最小值的标号int temp;//用来记录最大值/最小值for(int i=1;i<=cnt1;i++)//找满足条件的最大值{if(a[cnt]>up[i]){if(mark==-1){mark=i;temp=up[i];}else{if(temp<up[i]){mark=i;temp=up[i];}}}}if(mark!=-1)//若找到{temp=up[mark];up[mark]=a[cnt];dfs(cnt+1);up[mark]=temp;//记得回溯时还原状态}else//若没找到{up[++cnt1]=a[cnt];dfs(cnt+1);cnt1--;//同样回溯时还原状态}mark=-1;//初始化一下for(int i=1;i<=cnt2;i++)//找满足条件的最小值{if(a[cnt]<down[i]){if(mark==-1){mark=i;temp=down[i];}else{if(temp>down[i]){mark=i;temp=down[i];}}}}if(mark!=-1)//若找到，操作同上{temp=down[mark];down[mark]=a[cnt];dfs(cnt+1);down[mark]=temp;}else//若没找到，操作同上{down[++cnt2]=a[cnt];dfs(cnt+1);cnt2--;} }int main() { // freopen("input.txt","r",stdin);while(scanf("%d",&n)!=EOF&&n){for(int i=1;i<=n;i++)scanf("%d",a+i);ans=n;cnt1=cnt2=0;dfs(1);printf("%d\n",ans);}return 0; }

 

总结

以上是生活随笔为你收集整理的POJ - 3700 Missile Defence System.(dfs+最优性剪枝)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。