$\LARGE\color{orange}{刷题日记(算法提高课)}$

这题跟 AcWing 1010. 拦截导弹 类似，只不过拦截导弹是只能用下降子序列来覆盖，这题既可以用上升也可以用下降

类似的，我们定义 $up[i]$ 和 $down[i]$ 来表示上升数组和下降数组

注：上升子序列的结尾元素是单调递减的，下降子序列的结尾元素是单调递增的

但在元素的选择上，我们很难确定以哪种角度考虑当前元素（既可以选递增也可以选递减）

每一个元素都有两种选择，因此这里我们直接用 DFS 暴搜

在参数设计上，用一个参数表示当前元素下标，一个表示 $up$ 当中元素个数，一个表示 $down$ 当中元素个数

在递归之前要对现场进行保存，递归结束后要对现在进行恢复

下面给出两种 DFS 求最小值的做法：

全局变量：

#include <iostream>

using namespace std;

const int N = 55;
int a[N], up[N], down[N];//up表示下降子序列结尾元素，数组递增；down表示上升子序列结尾元素，数组递减
int n;
int cnt;

void dfs(int u, int cu, int cd)//u表示当前元素下标，cu表示下降子序列个数，cd表示上升子序列个数
{
    if(cu + cd >= cnt) return;//当前答案比已记录答案要大，直接返回
    if(u == n)
    {
        cnt = min(cnt, cu + cd);
        return;
    }

    int idx = 0;
    while(idx < cu && up[idx] <= a[u]) idx++;
    int t = up[idx];//对现场进行保存
    up[idx] = a[u];
    if(idx < cu) dfs(u + 1, cu, cd);
    else dfs(u + 1, cu + 1, cd);
    up[idx] = t;//恢复现场

    idx = 0;
    while(idx < cd && down[idx] >= a[u]) idx++;
    t = down[idx];
    down[idx] = a[u];
    if(idx < cd) dfs(u + 1, cu, cd);
    else dfs(u + 1, cu, cd + 1);
    down[idx] = t;

    return;
}

int main()
{
    while(cin >> n, n)
    {
        for(int i = 0; i < n; i++) cin >> a[i];
        cnt = n;//cnt初始赋最大值，最多就只有n个子序列

        dfs(0, 0, 0);

        cout << cnt << endl;

    }
    return 0;
}

迭代加深：

我们用一个变量 $depth$ 表示每次搜索的最大深度，每次不断增加，如果在当前搜索深度下能过找到答案，那么直接输出

相比第一种全局变量的方式，迭代加深找到的第一个结果就是最小值，之后便不需要再继续迭代了，而全局变量的方式会将所有的情况全部搜索完

#include <iostream>

using namespace std;

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

bool dfs(int depth, int u, int cu, int cd)//depth表示最大搜索深度，即此次搜索中，cu+cd的上限
{
    if(depth < cu + cd) return false;//当前的cu+cd超出搜索上限，表示搜索失败
    if(u == n) return true;//最后一个元素已经搜索完毕，表示此轮搜索满足题意

    //加入到up中
    int k = 0;
    while(k < cu && up[k] <= a[u]) k++;
    int t = up[k];
    up[k] = a[u];
    if(k < cu && dfs(depth, u + 1, cu, cd)) return true;
    else if(k >= cu && dfs(depth, u + 1, cu + 1, cd)) return true;
    up[k] = t;

    //加入到down中
    k = 0;
    while(k < cd && down[k] >= a[u]) k++;
    t = down[k];
    down[k] = a[u];
    if(k < cd && dfs(depth, u + 1, cu, cd)) return true;
    else if(k >= cd && dfs(depth, u + 1, cu, cd + 1)) return true;
    down[k] = t;

    return false;//如果前面都没有返回的话，表示此轮搜索失败
}

int main()
{
    while(cin >> n, n)
    {
        for(int i = 0; i < n; i++) cin >> a[i];

        int depth = 0;//所有序列组的个数上限

        while(!dfs(depth, 0, 0, 0)) depth++;//每次增加搜索深度

        cout << depth << endl;
    }
    return 0;
}