观察到这题n只有50，用dfs+剪枝来做

思路:

枚举每个数，分别加入最长上升子序列和最长下降子序列的情况中，$O(2^n)$

注意点：

1.回溯要正确
2.一定要加剪枝，本题剪枝可大大减少时间复杂度

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1005;
int n,a[N],ans;
int up[N],down[N];
void dfs(int cnt,int ulen,int dlen){
    if(ulen+dlen>=ans) return;
    if(cnt==n+1){
        ans=min(ans,ulen+dlen);
        return;
    }
    int idx,t;
    //上升子序列
    idx=upper_bound(up,up+ulen,a[cnt],greater<int>())-up;
    t=up[idx];up[idx]=a[cnt];
    if(idx==ulen) dfs(cnt+1,ulen+1,dlen);
    else dfs(cnt+1,ulen,dlen);
    up[idx]=t;
    //下降子序列
    idx=upper_bound(down,down+dlen,a[cnt])-down;
    t=down[idx];down[idx]=a[cnt];
    if(idx==dlen) dfs(cnt+1,ulen,dlen+1);
    else dfs(cnt+1,ulen,dlen);
    down[idx]=t;
}
int main(){
    while(scanf("%d",&n),n){
        for(int i=1;i<=n;i++) scanf("%d",&a[i]);
        ans=1e9;
        dfs(1,0,0);
        printf("%d\n",ans);
    }
    return 0;
}