C++(g++ 7.5.0) 解法, 执行用时: 213ms, 内存消耗: 396K, 提交时间: 2022-08-02 16:28:33

#include<bits/stdc++.h>
using namespace std;
const int N=66;
int n=1,a[N],up[N],down[N],s1,s2,ans=1e9;
void dfs(int x){
    if(s1+s2>=ans) return;
    if(x==n+1){
        if(s1+s2<ans) ans=s1+s2;
        return;
    }
    if(s1==0 || a[x]<=up[s1]){
        up[++s1]=a[x];
        dfs(x+1);
        s1--;
    }
    else{
        for(int i=1; i<=s1; i++){
            if(a[x]>up[i]){
                int tot=up[i];
                up[i]=a[x];
                dfs(x+1);
                up[i]=tot;
                break;
            }
        }
    }
    if(s2==0 || a[x]>=down[s2]){
        down[++s2]=a[x];
        dfs(x+1);
        s2--;
    }
    else{
        for(int i=1; i<=s2; i++){
            if(a[x]<down[i]){
                int tot=down[i];
                down[i]=a[x];
                dfs(x+1);
                down[i]=tot;
                break;
            }
        }
    }
}
int main(){
    while(cin>>n && n!=0){
        ans=1e9,s1=0,s2=0;
        for(int i=1; i<=n; i++){
            cin>>a[i];
        }
        dfs(1);
        cout<<ans<<endl;
    }
    return 0;
}

C++ 解法, 执行用时: 262ms, 内存消耗: 396K, 提交时间: 2022-02-05 18:40:32

#include<bits/stdc++.h>
using namespace std;
int up[51],dn[51],n,a[51],ans;
void dfs(int x,int y,int t){
	int i,tp;
    if(x+y>=ans)return;
    if(t>n){ans=min(ans,x+y);return;}
    for(i=1;i<=x;i++)if(up[i]<a[t])break;
    tp=up[i];
    up[i]=a[t];
    dfs(max(i,x),y,t+1);
    up[i]=tp;
    for(i=1;i<=y;i++)if(dn[i]>a[t])break;
    tp=dn[i];
    dn[i]=a[t];
    dfs(x,max(i,y),t+1);
    dn[i]=tp;
}
int main(){
    while(cin>>n&&n){for(int i=1;i<=n;i++)cin>>a[i],up[i]=0,dn[i]=0;ans=100000000;dfs(0,0,1);cout<<ans<<"\n";}
    return 0;
}