思路

DFS,迭代加深,剪枝,贪心，模仿y总的思路，可以利用贪心剪枝，用depth表示迭代，如果迭代完成，当前的depth是可以接受的，就是最优的，其他的请见y总题解。

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int a[N],up[N],dw[N],depth;
int n;
bool dfs(int depth,int u,int d,int t)
{
    if(depth<u+d)return false;
    if(t == n+1) return true;
    bool flag = false;
    for(int i=1;i<=u;i++)
    {
        if(up[i]<a[t])
        {
            int x = up[i];
            up[i] = a[t];
          if(dfs(depth,u,d,t+1))return true;
            up[i] = x;
            flag = true;
            break;
        }
    }
    if(!flag)
    {
        up[u+1]  = a[t];
     if(dfs(depth,u+1,d,t+1))return true;
    }
    flag = false;
    for(int i=1;i<=d;i++)
    {
        if(dw[i]>a[t])
        {
            int x = dw[i];
            dw[i] = a[t];
          if(dfs(depth,u,d,t+1))return true;
            dw[i] = x;
            flag = true;
            break;
        }
    }
    if(!flag)
    {
        dw[d+1]  = a[t];
     if(dfs(depth,u,d+1,t+1))return true;
    }
    return false;
}

int main()
{
   while(cin>>n){
       if(n==0)break;
    for(int i=1;i<=n;i++)
    cin>>a[i];
    depth = 0;
    while(!dfs(depth,0,0,1))depth++;
    cout<<depth<<"\n";
   }
}