最近在补全提高课所有题目的题解，宣传一下汇总的地方提高课题解补全计划

题目描述

题目给定一个长度为 n 的数组 w[n] ，要求我们用最少的上升子序列和下降子序列完全覆盖该数组

求该方案的上升子序列和下降子序列的总个数

解析

本题是对上题AcWing 1010. 拦截导弹的拓展

对于当前元素 w[i] 应该被加入到 上升子序列 还是 下降子序列 我们可以采用 暴力枚举 的方式

如果当前元素 w[i] 我们选择加入到 下降子序列 中，那么具体要加入到哪个 下降子序列 中
可以参考该篇博客 拦截导弹【附贪心证明】

如果加入到 上升子序列 中，那么具体要加入到哪个 上升子序列 中，方法类似加入 下降子序列 的

时间复杂度：$O(n2^n)$ 因此需要用到 迭代加深/维护全局最小值，剪枝 的优化

Code（维护全局最小值）

#include <iostream>
using namespace std;

// 这题是拦截拦截第二问的加强版
// 拦截导弹第二问是只考虑下降序列的方案数，因此直接用贪心搜出最优解即可(证明在那一题的笔记里)
// 这一题，确实要考虑下降和上升两种序列的方案数
// 因此只能用dfs进行爆搜两种方案的搭配，但无论是上升还是下降方案，依然采用上一题的贪心思路

const int N = 55;
int n;
int a[N];
int up[N], down[N];
int res;

//三个参数分别是考虑前u个导弹
//已经采用了上升系统个数sum_up
//和下降系统个数sum_down
void dfs(int u, int sum_up, int sum_down) {
    //如果已经超过了最优解答案，那么直接剪枝
    if (sum_up + sum_down >= res) return;
    //没有超过最优解答案，且把所有导弹都考虑到了
    //那他就是当前最优解了
    if (u == n) {
        res = sum_up + sum_down;
        return;
    }
    //情况一：考虑用上升拦截系统来拦截第u个导弹
    // 上升拦截系统的贪心思路是：
    //     如果当前已有的上升拦截系统的高度都大于第u个导弹高度，则重新开一套系统
    //     否则，则由当前低于第u个导弹最高拦截系统来负责拦截
    int k = 0;
    while (k < sum_up && up[k] >= a[u]) ++k;
    //找到了有这么个拦截系统
    int t = up[k]; //t用于dfs回溯的时候恢复现场
    up[k] = a[u];
    if (k >= sum_up) dfs(u + 1, sum_up + 1, sum_down);
    else dfs(u + 1, sum_up, sum_down);
    //恢复现场
    up[k] = t;

    //情况二：考虑用下降拦截系统来拦截第u个导弹
    // 下降拦截系统的贪心思路是：
    //     如果当前已有的下降拦截系统的高度都小于第u个导弹高度，则重新开一套系统
    //     否则，则由当前大于第u个导弹最低拦截系统来负责拦截
    k = 0;
    while (k < sum_down && down[k] <= a[u]) ++k;
    t = down[k]; //t用于dfs回溯的时候恢复现场
    down[k] = a[u];
    if (k >= sum_down) dfs(u + 1, sum_up, sum_down + 1);
    else dfs(u + 1, sum_up, sum_down);
    //恢复现场
    down[k] = t;
}

int main() {
    while (cin >> n, n) {
        for (int i = 0; i < n; ++i) cin >> a[i];
        //最差情况是n个导弹分别用n个系统拦截
        //因此可以设置res初始为n来设立哨兵
        res = n;
        dfs(0, 0, 0);
        cout << res << endl;
    }
    return 0;
}

Code（迭代加深）

#include <iostream>
using namespace std;

const int N = 55;
int n;
int w[N];
int up[N], down[N];

bool dfs(int u, int sum_up, int sum_down, int max_depth) {
    if (sum_up + sum_down > max_depth) return false;
    if (u == n) return true;

    int k = 0;
    while (k < sum_up && up[k] >= w[u]) ++ k;
    int t = up[k];
    up[k] = w[u];
    if (k == sum_up && dfs(u + 1, sum_up + 1, sum_down, max_depth)) return true;
    else if (k < sum_up && dfs(u + 1, sum_up, sum_down, max_depth)) return true;
    up[k] = t;

    k = 0;
    while (k < sum_down && down[k] <= w[u]) ++ k;
    t = down[k];
    down[k] = w[u];
    if (k == sum_down && dfs(u + 1, sum_up, sum_down + 1, max_depth)) return true;
    else if (k < sum_down && dfs(u + 1, sum_up, sum_down, max_depth)) return true;
    down[k] = t;

    return false;
}

int main() {
    while (cin >> n, n) {
        for (int i = 0; i < n; ++i) cin >> w[i];
        int depth = 0;
        while (!dfs(0, 0, 0, depth)) ++ depth;
        cout << depth << endl;
    }
    return 0;
}