算法

(DFS,迭代加深,剪枝,贪心) $O(n2^n)$

为了能遍历所有情况，我们首先考虑搜索顺序是什么。

搜索顺序分为两个阶段：

• 从前往后枚举每颗导弹属于某个上升子序列，还是下降子序列；
• 如果属于上升子序列，则枚举属于哪个上升子序列（包括新开一个上升子序列）；如果属于下降子序列，可以类似处理。

因此可以仿照AcWing 896. 最长上升子序列 II，分别记录当前每个上升子序列的末尾数up[]，和下降子序列的末尾数down[]。这样在枚举时可以快速判断当前数是否可以接在某个序列的后面。

注意这里的记录方式和上一题稍有不同：

• 这里是记录每个子序列末尾的数；
• 上一题是记录每种长度的子序列的末尾最小值。

此时搜索空间仍然很大，因此该如何剪枝呢？

对于第二阶段的枚举，我们可以仿照上一题的贪心方式，对于上升子序列而言，我们将当前数接在最大的数后面，一定不会比接在其他数列后面更差。
这是因为处理完当前数后，一定出现一个以当前数结尾的子序列，这是固定不变的，那么此时其他子序列的末尾数越小越好。

注意到按照这种贪心思路，up[]数组和down[]数组一定是单调的，因此在遍历时找到第一个满足的序列后就可以直接break了。

最后还需要考虑如何求最小值。因为DFS和BFS不同，第一次搜索到的节点，不一定是步数最短的节点，所以需要进行额外处理。
一般有两种处理方式：

• 记录全局最小值，不断更新； 这种搜索顺序可以参考@一瞬流年丶涅槃同学的题解；
• 迭代加深。一般平均答案深度较低时可以采用这种方式。后面的代码中采用的是这种方式。

时间复杂度

每个数在第一搜索阶段有两种选择，在第二搜索阶段只有一种选择，但遍历up[]和down[]数组需要 $O(n)$ 的计算量，因此总时间复杂度是 $O(n2^n)$。

C++ 代码

#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 60;

int n;
int h[N];
int up[N], down[N];

bool dfs(int depth, int u, int su, int sd)
{
    // 如果上升序列个数 + 下降序列个数 > 总个数是上限，则回溯
    if (su + sd > depth) return false;
    if (u == n) return true;

    // 枚举放到上升子序列中的情况
    bool flag = false;
    for (int i = 1; i <= su; i ++ )
        if (up[i] < h[u])
        {
            int t = up[i];
            up[i] = h[u];
            if (dfs(depth, u + 1, su, sd)) return true;
            up[i] = t;
            flag = true;
            break;  // 注意由上述证明的贪心原理，只要找到第一个可以放的序列，就可以结束循环了
        }
    if (!flag)  // 如果不能放到任意一个序列后面，则单开一个新的序列
    {
        up[su + 1] = h[u];
        if (dfs(depth, u + 1, su + 1, sd)) return true;
    }

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

    return false;
}

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

        int depth = 0;
        while (!dfs(depth, 0, 0, 0)) depth ++ ;     // 迭代加深搜索

        cout << depth << endl;
    }

    return 0;
}