C++ 代码

// /*
//     要么一直上升，要么一直下降，所以对于每个元素，不知道他是在上升的序列中
//     还是下降的序列中，所以每个元素都要枚举他所有能放的序列，包括上升的和下降的

//     在扩展节点的时候，还是使用了一个贪心策略，大大节省了时间
//     假设现在要把一个数放到上升序列中，那么一定要放在所有上升序列中国最后一个元素最大
//     的那个序列，因为放着小的，还留着放后边的较小的元素呢？为什么要把这个小的给浪费了呢
//     其实和上一道题类似，up[i]其实已经是按照这种策略排好序的了，所以只用找最先碰到的那个就行了
// */

// #include<iostream>
// #include<cstring>

// using namespace std;

// const int N=55;

// int a[N];
// int ans;
// int up[N], down[N];//分别存放上升和下降的各个子序列的最后一个元素
// int n;

// void dfs(int u, int d, int t)//u为上升序列的个数， d为下降， t表示是第k个数
// {
//     if(u+d >=ans) return; //剪枝优化，上升和下降的加再一起超过当前的ans就退出的

//     //递归出口
//     if(t == n)
//     {
//         if(u+d < ans)  ans=u+d;//ans存放一个最小值
//         return;
//     }

//     //上升的情况
//     int i;
//     for(i=1; i<=u; i++)//找到第一个末尾数小于a[t]的那个序列 
//         if(up[i] < a[t]) break;

//     int temp=up[i];//存一下，回复现场的时候要用
//     up[i]=a[t];//添加到该系统中
//     //向下搜索
//     //i最后可能是等于u+1的，如果没有找到一个合适的序列属于他
//     dfs(max(u, i), d, t+1);
//     up[i]=temp;

//     //下降的情况
//     for(i=1; i<=d; i++) 
//         if(down[i] > a[t]) break;
//     temp=down[i];
//     down[i]=a[t];//添加进去
//     dfs(u, max(d, i), t+1);
//     down[i]=temp;

// }

// int main()
// {
//     // while(scanf("%d", &n) != EOF && n!=0)
//     while(cin>>n, n)
//     {
//         ans=100;
//         for(int i=0; i<n; i++)
//             cin>>a[i];
//         dfs(0, 0, 0);
//         printf("%d\n", ans);
//     }


//     return 0;
// }

//还有一种DFS求最小值的方法，上一种是用一个全局变量
//记录，这一种是迭代加深，一般平均答案深度较低时可以采用这种方式

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=60;

int n;
int h[N];
int up[N], down[N];

//参数是总序列的数量， 当前点的位置， 上升和下降序列的数量
bool dfs(int depth, int u, int su, int sd)
{
    //如果上升序列个数+下降序列个数 > 总个数上限， 则回溯
    if(su+sd>depth) return false;
    //到最后一个的后边的，就退出
    if( u == n) return true;

    //枚举放到上升子序列中的情况
    bool flag=false;
    for(int i=1; i<=su; i++)
        if(up[i] < h[u])
        {
            int t=up[i];
            up[i]=h[u];
            //不需要多开一个序列了
            if(dfs(depth, u+1, su, sd)) return true;
            up[i]=t;
            flag=true;
            break;//由贪心原理， 只要找到第一个可以放的序列，就可以结束循环了
        }
    if(!flag)//如果不能放到任意一个序列后边，就新开一个
    {
        up[su+1]=h[u];
        //depth存的是上限， 所以depth不用再变了
        if(dfs(depth, u+1, su+1, sd)) return true;
    }

    //枚举放到下降子序列中的情况
    flag=false;
    for(int i=1; i<=sd; i++)
        if(down[i] > h[u])
        {
            int t=down[i];
            down[i]=h[u];
            if(dfs(depth, u+1, su, sd)) return true;
            down[i]=t;
            flag=true;
            break;
        }
    if(!flag)
    {
        down[sd+1] = h[u];
        if(dfs(depth, u+1, su, sd+1)) return true;
    }

    return false;

}

int main()
{
    while(cin>>n, n)
    {
        for(int i=0; i<n; i++) cin>>h[i];

        //depth记录总序列的个数的上限
        int depth=0;
        //如果从0位置开始， 上升和下降序列的数量都是0开始搜索不行，就把总的长度+1，继续下一轮
        while(!dfs(depth, 0, 0, 0)) depth++;//迭代加深搜索

        cout<<depth<<endl;
    }

    return 0;
}