题解

看到 n 极小的数据范围，就该知道，此题可能要用爆搜去做。

对于每个导弹都有两个决策，一是进入上升子序列，二是进入下降子序列，而在做完进入哪个子序列这个决策后还有两个小决策，一是进入已有序列，而是建立新序列。所有每个导弹有 $4$​ 个决策。

对于每一个序列，我们只需要知道其末尾高度是多少就够了，故用 $u[], d[]$ 维护。

可以用 $u[]$ 储存每一个上升序列的末尾高度，$d[]$ 同理。

而我们的 dfs维护三个值，$cnt$：当前对第 $cnt$ 个导弹进行决策，$cu$：当前有$cu$个上升子序列，$cd$：当前有$cd$个下降子序列。

当决策完 $n$ 个导弹后，$cu + cd$ 的最小值即是答案。

而决策的过程，在 $cnt$ 个导弹进行决策时，若它进入上升子序列，此时要运用贪心的思想，即该导弹最好进入已有的序列，进入已有的序列最好进入，与序列末尾其高度相差最小的的序列，简单来说，就是要进入在序列末尾比 $cnt$ 导弹高度小的序列末尾最高的子序列中，若没有序列末尾比 $cnt$ 小的序列末尾，则 $cnt$ 新建一个上升子序列。

进入下降子序列的决策过程类似，偷懒一波，不予分析。

再分析一波时间复杂度，因为无论是进入上升子序列还是进入下降子序列，进入已有序列和建立新序列都是冲突的，这两个小决策只会选一个，故每一次的 $dfs$ 只会搜两个决策，而在做决策之前都要遍历一个 $u[]$ 或 $d[]$，故时间复杂度是 $O(n*2^n)$。

$n$ 最高为 $50$，咋一看比超时，但只需要在暴搜的时候做剪枝就不会超时了，在暴搜的时候如果当前的 $cu + cd >= res$，那么该情况必定无法比当前的 $res$ 更优，所以直接剪枝

C++ 代码

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

#define ll long long
#define fi first
#define se second
#define i128 __int128
typedef pair<int,int>PII;
typedef pair<int,char>PIC;
typedef pair<int,PII>PIII;

const int N = 55, mod = 1000000007;
int a[N];
int u[N], d[N];
int res;
int n;
void dfs(int cnt, int cu, int cd){
    if(cu + cd >= res)
        return ;

    if(cnt == n){
        res = cu + cd;
        return;
    }

    int k = 0;
    while(k < cu && a[cnt] <= u[k])
        k++;
    if(k < cu){
        int temp = u[k];
        u[k] = a[cnt];
        dfs(cnt + 1, cu, cd);
        u[k] = temp;
    }
    else{
        u[cu] = a[cnt];
        dfs(cnt + 1, cu + 1, cd);
    }


    k = 0;
    while(k < cd && a[cnt] >= d[k])
        k++;
    if(k < cd){
        int temp = d[k];
        d[k] = a[cnt];
        dfs(cnt + 1, cu, cd);
        d[k] = temp;
    }
    else {
        d[cd] = a[cnt];
        dfs(cnt + 1, cu, cd + 1);
    }

}



void solve(){
    res = n;

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

    cout << res << '\n';
    return;
}


signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    while(cin >>n){
        if(n == 0)
            break;
        solve();
    }

    return 0;
}