【导弹防御系统】

一套防御系统的导弹拦截高度要么一直严格单调上升，要么一直严格单调下降。例如，一套系统先后拦截了高度为 3 和高度为 4 的两发导弹，那么接下来该系统就只能拦截高度大于 4 的导弹。

给定即将袭来的 $n(n\leq 50)$ 颗导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

【题解】

up[i] 和 down[i] 记录第 i 套上升和下降系统拦截的最后一个导弹高度。

dfs(u,su,sd) 表示当前正在处理第 u 个数据，已有 su 个上升，sd 个下降。

暴力：将每个导弹都放入所有系统进行尝试。

这里明显存在贪心策略，以 up 为例，如果能将元素放入大的里面，就不必浪费小的，于是考虑对 up 与 down 排序。但其实 up 和 down 按这种策略进行的时候已经排好序的了，只用找最前面的合法的即可。

为什么说这种策略已经排好序了呢？

以 up 为例，如果不存在 up[i] > a[u]，那么需要新开 up[j]，此时 up[i] > up[j]。也就是说新开的元素一定小于原本的数据，而开始的时候只有一个元素 up[1]，所以整个 up 序列是严格单调递减的。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6 + 10, INF = 0x3f3f3f3f;
int n, a[N], ans, up[N], down[N];

void dfs(int u, int su, int sd) {
    if (su + sd >= ans) return;
    if (u > n) {
        ans = su + sd; return;
    }
    // sort(up + 1, up + 1 + su, [](int& l, int& r) { return l > r; });
    // sort(down + 1, down + 1 + sd, [](int& l, int& r) { return l < r; });
    int i = 0;
    for (i=1; i <= su; i++) if (up[i] < a[u]) break;
    int t = up[i];
    up[i] = a[u], dfs(u + 1, max(su, i), sd);
    up[i] = t;

    for (i=1; i <= sd; i++) if (down[i] > a[u]) break;
    t = down[i];
    down[i] = a[u], dfs(u + 1, su, max(sd, i));
    down[i] = t;
}
int main() {
    while (scanf("%d", &n) && n) {
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        ans = n, dfs(1, 0, 0);
        printf("%d\n", ans);
    }
    return 0;
}