题意 问最少有多少个上升子序列 和下降子序列 可以覆盖一个序列
#include<bits/stdc++.h> using namespace std; const int N=100; int a[N],up[N],down[N]; int n; bool dfs(int depth,int u,int su,int sd){ if(su+sd>depth) return false; if(u==n) return true; // 枚举所有可能的true； // up 数组； bool flag = false; for(int i=1;i<=su;i++){ if(a[u] > up[i]) { int t=up[i]; up[i] = a[u]; if(dfs(depth,u+1,su,sd)) return true; up[i]=t; flag = true; break; } } if(!flag) { up[su+1] =a[u]; if(dfs(depth,u+1,su+1,sd)) return true; } // 枚举下降 flag = false; for(int i=1;i<=sd;i++) { if(a[u] < down[i]) { int t=down[i]; down[i]= a[u]; if(dfs(depth,u+1,su,sd)) return true; down[i] = t; flag = true; break; } } if(!flag) { down[sd+1] = a[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>>a[i]; } int depth=0; while(!dfs(depth,0,0,0)) depth++; cout<<depth<<endl; } return 0; }