维护全局最小值法

#include<bits/stdc++.h>
using namespace std;
const int N=55;
int n,ans;
int a[N],up[N],down[N];

void dfs(int k,int u,int d)
{
    if(u+d>=ans)return;
    if(k==n)
    {
        ans=u+d;
        return;
    }

    int cnt=0;

    while(up[cnt]<=a[k] && cnt<u)cnt++;
    int t = up[cnt];
    up[cnt]=a[k];
    if(cnt<u)dfs(k+1,u,d);
    else dfs(k+1,u+1,d);
    up[cnt]=t;

    cnt=0;
    while(down[cnt]>=a[k] && cnt<d)cnt++;
    t=down[cnt];
    down[cnt]=a[k];
    if(cnt<d)dfs(k+1,u,d);
    else dfs(k+1,u,d+1);
    down[cnt]=t;

}

int main()
{

    while(cin>>n,n)
    {
        for(int i=0;i<n;i++)cin>>a[i];
        ans=n;
        dfs(0,0,0);

        cout<<ans<<endl;
    }

    return 0;
}