导弹防御系统 https://www.acwing.com/problem/content/189/

在拦截导弹的基础上，多了上升子序列的选择
即用上升子序列和下降子序列覆盖全部数，且子序列最少

贪心流程

从前往后扫描每个数，对于每个数

1.
如果现有的子序列的结尾都小于当前数，则创建新的子序列
否则将当前数放到结尾大于等于他的最小的子序列后面
2.
如果现有的子序列的结尾都大于当前数，则创建新的子序列
否则将当前数放到结尾小于等于他的最大的子序列后面

用dfs遍历以上两种情况

up数组表示所有严格上升子序列的结尾，它本身随下标是非严格单调下降的
down数组表示所有严格下降子序列的结尾，它本身随下标是非严格单调上升的

这里是记录每个子序列末尾的数
上一题是记录每种长度的子序列的末尾最小值

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 55;
int a[N], up[N], down[N];
int n, res;

void dfs(int u, int su, int sd)
{
    if ( su + sd >= res ) return;
    if ( u == n )
    {
        res = su + sd;
        return;
    }
    int k = 0;
    while ( k < su && up[k] >= a[u] ) k ++;
    int t = up[k];
    up[k] = a[u];
    if ( k < su ) dfs(u + 1, su, sd);
    else dfs(u + 1, su + 1, sd);
    up[k] = t;

    k = 0;
    while ( k < sd && down[k] <= a[u] ) k ++;
    t = down[k];
    down[k] = a[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 >> a[i];
        res = n;
        dfs(0, 0, 0);
        cout << res << endl;
    }
    return 0;
}