拦截导弹 + dfs

#include <iostream>

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)  // u:当前枚举到哪个数,su:上升子序列的个数,sd:下降子序列的个数
{
    if(su + sd >= ans) return ; // 剪枝，不可能再更新了，直接return
    if(u==n) // 递归结束
    {
        ans = su + sd;
        return ;
    }

    // 情况1：将当前数放到上升子序列中
    int k =0;
    while(k < su && up[k] >= q[u]) k++;  // 因为序列下标是从0开始的，所以是<
    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;
    }

    return 0;
}