导弹防御系统

题目描述：

为了对抗附近恶意国家的威胁，R 国更新了他们的导弹防御系统。

一套防御系统的导弹拦截高度要么一直 严格单调 上升要么一直 严格单调 下降。

例如，一套系统先后拦截了高度为 33 和高度为 44 的两发导弹，那么接下来该系统就只能拦截高度大于 44 的导弹。

给定即将袭来的一系列导弹的高度，请你求出至少需要多少套防御系统，就可以将它们全部击落。

思路：

因为不知道每个导弹到底是属于第一种导弹还是第二种导弹，所以需要进行枚举，可以用dfs来写，结合贪心 + 二分

dfs有三个参数，dfs(u, a, b),表示当时是第u个数，用了a个上升导弹，b个下降导弹

如果a + b >= ans,就表明不会产生更优的答案，可以返回，这是一个很重要的剪枝

对于当前这个点，我们先将其放在上升导弹里面，去贪心选第一个大于tr[u]的点，把他更新成tr[u]，因为上升导弹序列存的是从大到小的数，所以二分的时候要加一个参数greater<int>()，注意如果没有符合的导弹，就说明需要一个新的上升导弹，更新一下a的参数,其他的细节自己看吧，下降导弹也是类似的道理

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod 1000000007
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
int n, m, k;
int tr[MAX];
int up[105];
int down[105];
int ans;

void dfs(int u, int a, int b){
    if(a + b >= ans)return;
    if(u == n + 1){
        ans = a + b;
        return;
    }
    
    // 放到上升序列
    if(tr[u] < up[a] || a == 0){
        up[a + 1] = tr[u];
        dfs(u + 1, a + 1, b);
        up[a + 1] = 0;
    }
    else {
        int p = (int)(lower_bound(up + 1, up + a + 1, tr[u], greater<int>()) - up);
        int x = up[p];
        up[p] = tr[u];
        dfs(u + 1, a, b);
        up[p] = x;
    }
    
    //放到下降序列
    if(tr[u] > down[b] || b == 0){
        down[b + 1] = tr[u];
        dfs(u + 1, a, b + 1);
        down[b + 1] = 0;
    }
    else{
        int p = (int)(lower_bound(down + 1, down + b + 1, tr[u])-down);
        int x = down[p];
        down[p] = tr[u];
        dfs(u + 1, a, b);
        down[p] = x;
    }
}

void work(){
    while(cin >> n && n){
        mem(up, 0);mem(down, 0);
        for(int i = 1; i <= n; ++i)cin >> tr[i];
        ans = n;
        dfs(1, 0, 0);
        cout << ans << endl;
    }
   
}


int main(){
    io;
    work();
    return 0;
}