• 【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

    完整代码

    1. #include
    2. using namespace std;
    3. const int N=55;
    4. int res;
    5. int h[N],up[N],down[N];
    6. int n;
    7. void dfs(int u,int su,int sd)
    8. {
    9. if(su+sd>=res)return;
    10. if(u==n)
    11. {
    12. res=su+sd;
    13. return;
    14. }
    15. int k=0;
    16. while(kh[u])k++;
    17. if(k
    18. {
    19. int t=up[k];
    20. up[k]=h[u];
    21. dfs(u+1,su,sd);
    22. up[k]=t;
    23. }
    24. else
    25. {
    26. up[k]=h[u];
    27. dfs(u+1,su+1,sd);
    28. }
    29. k=0;
    30. while(k
    31. if(k
    32. {
    33. int t=down[k];
    34. down[k]=h[u];
    35. dfs(u+1,su,sd);
    36. down[k]=t;
    37. }
    38. else
    39. {
    40. down[k]=h[u];
    41. dfs(u+1,su,sd+1);
    42. }
    43. }
    44. int main()
    45. {
    46. while(cin>>n,n)
    47. {
    48. for(int i=0;i>h[i];
    49. res=n;
    50. dfs(0,0,0);
    51. cout<
    52. }
    53. return 0;
    54. }

  • 相关阅读:
    C#学习笔记--变量类型的转换
    Spring设计模式,事务管理和代理模式的应用
    kafka部分partition的leader=-1修复方案整理
    vue使用slot封装navBar
    无涯教程-JavaScript - DEC2BIN函数
    HUAWEI 华为交换机 配置 MAC 地址漂移检测示例
    开发信群发技巧有哪些?外贸邮件怎么群发?
    【力扣精选算法100道】——二进制求和
    地质灾害防治可视化智慧管理系统平台
    DLP迈向NG DLP的进化之路
  • 原文地址:https://blog.csdn.net/m0_63222058/article/details/133695895