思路在代码里

代码

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=55;
int up[N],down[N];
int ans,q[N];
int n;
void dfs(int u,int st,int sd){
    if(st+sd>=ans){//如果此时已经大于ans了，那么最后这条路径的结果肯定大于ans，所以不用走了
        return;
    }
    if(u==n){
        ans=min(ans,st+sd);
        return ;
    }
    int k=0;
    while(k<st&&up[k]>=q[u])k++;//在上升子序列结尾中找到第一个小于q[u]的数，
    int t=up[k];//用一个t来存下将要被改变的数，dfs后可“回复现场”
    up[k]=q[u];
    if(k<st)dfs(u+1,st,sd);//如果没有开拓新上升子序列，上升子序列的结尾个数不变
    else dfs(u+1,st+1,sd);//反之则变
    up[k]=t;//回复现场
    k=0;//重新初始化
    while(k<sd&&down[k]<=q[u])k++;//同理，在下降子序列结尾中找到第一个大于q[u]的数
    t=down[k];
    down[k]=q[u];
    if(k<sd) dfs(u+1,st,sd);
    else dfs(u+1,st,sd+1);
    down[k]=t;
}
int main(){
    while(cin >> n,n){
        memset(up,0,sizeof up);//初始化
        memset(down,0,sizeof(down));
        ans=n;
        for(int i=0;i<n;i++){
            cin >> q[i];
        }
        dfs(0,0,0);
        cout << ans << endl;
    }
}