概述

该题也是一个典型的最长上升子序列的问题。

条件： 导弹拦截高度要么一直上升要么一直下降。

有的导弹可以选择上升，有的可以选择下降，不是单纯地问所存在的序列可以划分为多少组上升子序列的问题，所以不能用之前的方法解。

怎么做？
当找不到办法时，考虑使用枚举法

如何做？
从问题的解出发，最终问题的答案是有许多单调上升子序列和许多单调下降子序列，那么实际就是对于每个数，来思考将该数放到上升序列中还是下降序列中。

题解

注意顺序性

• 依次枚举每个数
  > 先枚举将该数作为单调上升的序列，还是单调下降的序列中
  1. 如果该数被放到了单调上升的序列中，则枚举将该数放到哪个单调上升的序列后面
  2. 如果该数被放到了单调下降的序列中，则枚举将该数放到哪个单调下降的序列后面。
  3. 或者该数成为一个单独的单调序列

     实际上来看这就是一个建模问题，首先建模为初始状态，初始状态可以经过很多离散步骤到达一个新的状态，最终不断地到达目的状态。

暴力，考虑搜索空间，首先如果搜索的序列是有序的，那么就可以使用二分法。每一步搜索空间是50，那么这样下去，就是5050…, 最终是指数级别

up[] 存储当前所有上升子序列的末尾元素
down[] 存储当前所有下降子序列的末尾元素

所以这里实际上用到了上一题导弹防御的结果来做，对于多个单调上升（下降）子序列只需要对末尾元素进行考虑即可。
这一点真厉害！！！
然后这里又可以进行优化

使用贪心的思想
x 尽可能覆盖一个末尾元素大的序列

因此是一个很强的优化，所以每一步实际上只有两种选择，要么上升，要么下降。

up本身是单调的，所以一方面找到即停止，另一方面可以直接考虑用二分

如何进行搜素
1. 使用BFS, BFS是宽度优先，需要进行存储（空间太多，不太好剪枝），而且代码写起来比较麻烦
2. 使用DFS, 一种想法是使用全局变量，第二种方式是迭代加深

代码

dfs 560ms 时间O(n2^n) 空间O(n)

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 55;

int n;
int q[N];
int up[N], down[N];
int ans;

void dfs(int u, int su, int sd) {
    if (su + sd >= ans) return; // ans不可能再小了

    if (u == n) {
        ans = su + sd;  // su, sd 分别表示 len(up[]), len(down[])
        return;
    }

    // 情况1：将当前数放到上升子序列中
    int k = 0;
    while (k < su && up[k] >= q[u]) k ++;
    int t = up[k];
    up[k] = q[u];
    if (k < su) dfs(u + 1, su, sd);
    else dfs(u + 1, su + 1, sd);
    up[k] = t;

    // 情况2：将当前数放到下降子序列中。
    k = 0;
    while (k < sd && down[k] <= q[u]) k ++;
    t = down[k];
    down[k] = q[u];
    if (k < sd) dfs(u + 1, su, sd);
    else dfs(u + 1, su, sd + 1);
    down[k] = t;
}

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

        ans = n;
        dfs(0, 0, 0);

        cout << ans << endl;
    }
}

迭代加深+普通 541ms 时间O(n2^n) 空间O(n)

#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) {
    // depth 序列上限, su, sd, u 上一个数或者下一个数
    if (su + sd > depth) return false;  // 9 > 8, 深度从0开始
    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;
}

迭代加深+二分 443ms 时间O(logn 2^n) 空间O(n)

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

using namespace std;

const int N = 55;

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

bool dfs(int depth, int u, int su, int sd) {
    if (su + sd > depth) return false;
    if (u == n) return true; // u表示的是枚举每个顶点

    if (!su || up[su] >= a[u]) {
        up[su + 1] = a[u];
        if (dfs(depth, u + 1, su + 1, sd)) return true;
    } else {
        int l = 1, r = su;
        while (l < r) { // 坐标
            int mid = (l + r) >> 1;
            if (up[mid] < a[u]) r = mid;
            else l = mid + 1;
        }
        int t = up[l];
        up[l] = a[u];
        if (dfs(depth, u + 1, su, sd)) return true;
        up[l] = t;
    }

    if (!sd || down[sd] <= a[u]) {
        down[sd + 1] = a[u];
        if (dfs(depth, u + 1, su, sd + 1)) return true;
    } else {
        int l = 1, r = sd;
        while (l < r) {
            int mid = (l + r) >> 1;
            if (down[mid] > a[u]) r = mid;
            else l = mid + 1;
        }
        int t = down[l];
        down[l] = a[u];
        if (dfs(depth, u + 1, su, sd)) return true;
        down[l] = 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;
}