AcWing 187. 导弹防御系统

题目传送门

一、 迭代加深

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

\(Lis\)中，最核心的思想在于能否将一个元素加入到序列中，只与这个序列目前的最后一个元素有关,这道题就用了这个关键的思想。

用\(up[k]\)和\(down[k]\)记录第\(k\)套上升（下降）系统目前所拦截的最后一个导弹,\(dfs(u,v,t)\)意味着已有\(u\)个上升，\(v\)个下降，正在处理第\(t\)个数。

按理说，每拿到一个新的数字应该将它所有能放入的序列都放一遍的,但扩展节点时却存在一个贪心策略，大大节省了时间。

假设现在要把一个数放入一个上升序列，那么一定是所有能放入的上升序列中，最后一个元素最大的那一个。其实想想也是，既然每个数字都要放到一个序列中，对于上升序列，肯定是目前越小越有用，既然能放入大的里面，何必浪费一个小的呢。注意到其实\(up[i]\),\(down[i]\)按这种策略已经是排好序的了，所以只用找最先碰到的一个就行了

二、实现代码

#include 

using namespace std;
const int N = 60;

int n;        //数据组数
int a[N];     //结果数组
int up[N];    //多组上升序列，up[i]保存第i套防御系统的最后一个高度值
int down[N];  //多组下降序列，down[i]保存第i套防御系统的最后一个高度值
int depth;    //正在探测的所需的防御系统数量,最终停留的值，就是最小数量

/**
 * 功能：迭代加深
 * @param k k号索引数，a[k]
 * @param u 上升子序列的个数
 * @param v 下降子序列的个数
 * @return 是不是在规定好的depth套防御系统的限定下，完成了拦截所有导弹的目标
 */
bool dfs(int k, int u, int v) {
    // 如果上升序列个数 + 下降序列个数 > 限定的总个数
    if (u + v > depth) return false;
    //如果成功到达最后，则表示成功！最后一个应该是a[k-1]，如果成功完成填充a[k-1]，就表示完成了所有填充工作
    if (k == n) return true;
    //每个数字有两种选择：(1)放入某个上升子序列，(2)放入某个下降子序列

    // 尝试放入上升子序列
    bool flag = false;
    //枚举每个上升子序列
    for (int i = 1; i <= u; i++)
        //如果可以填充到当前序列最后
        if (up[i] < a[k]) {
            //标识找到
            flag = true;
            //放到临时变量中,用于恢复现场
            int x = up[i];
            //放在找到的第i套系统的最后，修改记录的最后值
            up[i] = a[k];
            //继续迭代加深
            if (dfs(k + 1, u, v)) return true;
            //恢复现场
            up[i] = x;
            break;  // 注意由上述证明的贪心原理，只要找到第一个可以放的序列，就可以结束循环了
        }
    // 如果不能放到任意一个序列后面，则单开一个新的序列
    if (!flag) {
        up[u + 1] = a[k];
        if (dfs(k + 1, u + 1, v)) return true;
    }

    //尝试放入下降子序列
    flag = false;
    // 枚举每个下降子序列
    for (int i = 1; i <= v; i++)
        if (down[i] > a[k]) {
            int x = down[i];
            down[i] = a[k];
            if (dfs(k + 1, u, v)) return true;
            down[i] = x;
            flag = true;
            break;  // 注意由上述证明的贪心原理，只要找到第一个可以放的序列，就可以结束循环了
        }
    // 如果不能放到任意一个序列后面，则单开一个新的序列
    if (!flag) {
        down[v + 1] = a[k];
        if (dfs(k + 1, u, v + 1)) return true;
    }
    //无解的情况
    return false;
}

int main() {
    //多组数据，输入0时结束
    while (cin >> n, n) {
        //读入数据
        for (int i = 0; i < n; i++) cin >> a[i];
        //迭代加深
        for (depth = 0;; depth++)
            if (dfs(0, 0, 0)) break;
        //输出结果
        printf("%d\n", depth);
    }
    return 0;
}