思路分析

本题和上一题的区别是，上一题求出最少的上升或者下降的子序列即可，而本题要求出最少的上升和下降的子序列的和，故本题才用的方法和上题不同，本题比较如果能想出序列中任意一个元素要么属于上升序列，要么属于下降序列，那么就可以很容易的想到暴力的方法（枚举所有方案）得出最优解。

但是如何优化呢，首先每个元素要么属于上升子序列要么属于下降子序列，这点是没法优化的，优化的地方在于属于上升或者下降的子序列时，如何快速找出属于哪个子序列，这点就可以用上一题的思想了，就是用贪心的方法， 以上升子序列为例，插入到小于当前元素的所有上升子序列中末尾元素最大的那个就是最优的，值得我们注意的地方就是up数组（所有上升子序列的末尾元素组成的）是单调下降的，这点自己列举几个数分析一下就可以看出来

C++ 代码

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 60;

int arr[N];
int up[N], down[N];
int n;
int ans;

void dfs(int index, int u, int d){
    if(index == n + 1){
        ans = min(ans, u + d);
        return;
    }
    if(u + d >= ans) return;//提前回溯
    //放在up里， up是单调下降的
    if(arr[index] < up[u]) {
        up[++u] = arr[index];
        dfs(index+1, u, d);
        --u;
    }
    else{
        for(int i = 1;i <= u;++i){
            if(arr[index] > up[i]){
                int t = up[i];
                up[i] = arr[index];
                dfs(index+1, u, d);
                up[i] = t;
                break;
            }
        }
    }
    //放在down里，down是单调上升的
    if(arr[index] > down[d]){
        down[++d] = arr[index];
        dfs(index+1, u, d);
        --d;
    }else{
        for(int i = 1;i <= d;++i){
            if(arr[index] < down[i]){
                int t = down[i];
                down[i] = arr[index];
                dfs(index+1, u, d);
                down[i] = t;
                break;
            }
        }
    }
    return;
}

int main(){
    while(cin >> n, n){
        for(int i = 1;i <= n;++i) cin >> arr[i];
        up[0] = 0x3f3f3f3f, down[0] = -0x3f3f3f3f;
        ans = 100;
        dfs(1, 0, 0);        
        cout << ans << endl;
    }    
}