AcWing 187. 导弹防御系统

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 187. 导弹防御系统原题链接困难

作者：

一瞬流年丶涅槃 , 2019-08-20 23:42:38 , 所有人可见 , 阅读 8914

135

38

题解：

导弹防御系统很自然的想到LIS算法，不过这里的条件是一套防御系统的导弹拦截高度要么一直上升要么一直下降，所以用LIS算法是不正确的

而LIS中，最核心的思想在于能否将一个元素加入到序列中，只与这个序列目前的最后一个元素有关
这道题就用了这个关键的思想。
用up[k]和down[k]记录第k套上升（下降）系统目前所拦截的最后一个导弹
dfs(u,v,t)意味着已有u个上升，v个下降，正在处理第t个数

按理说，每拿到一个新的数字应该将它所有能放入的序列都放一遍的
但扩展节点时却存在一个贪心策略，大大节省了时间。
假设现在要把一个数放入一个上升序列，那么一定是所有能放入的上升序列中，最后一个元素最大的那一个。
其实想想也是，既然每个数字都要放到一个序列中，
对于上升序列，肯定是目前越小越有用，既然能放入大的里面，何必浪费一个小的呢
注意到其实up[i]按这种策略已经是排好序的了，所以只用找最先碰到的一个就行了

C++ 代码

#include<iostream>
using namespace std;
const int N = 55;
int a[N], ans, up[N], down[N], n;
void dfs(int u, int d, int t)  //u表示上升的系统个数，d表示下降的系统个数,t表示第t个数
{
    if(u + d >= ans) return ;
    if(t ==  n){
        if(u + d < ans)ans = u + d;
        return ;
    }
    int i;
    for(i = 1; i <= u; i++)  //找到第一个末尾数小于a[t]的导弹系统
        if(up[i] < a[t])break;

    int temp = up[i];
    up[i] = a[t];//添加到该导弹系统中
    dfs(max(u, i), d, t + 1);
    up[i] = temp;  //恢复现场
    for(i = 1; i <= d; i++)//找到第一个末尾数大于a[t]的导弹系统
        if(down[i] > a[t])break;
    temp = down[i];
    down[i] = a[t];//添加到该导弹系统中去
    dfs(u, max(d, i), t + 1);
    down[i] = temp;//恢复现场
}
int main()
{
    while(scanf("%d", &n) != EOF && n != 0){
        ans = 100;
        for(int i = 0; i < n; i++)
            cin >> a[i];
        dfs(0, 0, 0);
        printf("%d\n", ans);
    }
    return 0;
}

61 评论

圆梦背影 2022-12-23 12:49

看完题解感觉这个题好简单啊🤣

G_83 2023-06-01 14:53

大佬，想问一下，为什么说“up[i]按这种策略已经是排好序的了”，为啥有序啊

我是小啾啾呀 2023-06-22 17:27 回复了 G_83 的评论

比方说，我们创造up新序列的时机就是已有序列的最后一个数都大于当前要插入的数，即新序列的最后一个数一定是小于所有序列的最后一个数，那么从一开始，第二个序列的最后一个数小于第一个序列的，以此类推，所有已有的up序列就按照最后一个数的大小从大到小排列了。

Cplusplus 2023-04-29 20:15

你被点名啦

Toxic_3 2023-09-16 17:01

这里补充一下大佬的剪枝思路，一开始我整体分了4大类；
1.放入up；
2放入down；
3新开一个up；
4新开一个down；
这样也能过，但是大佬直接分成了两种情况
1.放入up，如果拦截不了，开一个新up；
2放入down，如果拦截不了，开一个新的down；
具体逻辑就是，如果你的up能够拦截，就一定不需要再开一个up；
例如假设你的up[1, 2, 3]是4， 3， 2，现在来了个6，我们放在up[1]的位置就变成了6，3，2
而开一个新的up就变成了4， 3， 2， 6；
这样的话第一，新的拦截系统不符合我们贪心思路的有序，
第二，我们分情况讨论，如果接下来的导弹都比6小，根本用不到6，就相当于多开，如果有比6大的，要一直到拦截系统前面的数都比6大， 6才会发挥作用，假设6可以发挥作用时，需要拦截的数是x，如果之前6在4后面，那么这个大数就会是一个新的拦截系统，如果在6被新开了，那么这个大数就在6后面，这样的话就没有任何区别