题解 | #合唱队形#

#include <iostream>
using namespace std;
void longestIncrease(int a[],int l,int r){
    int n=r-l+1;
    if(n==0) return ;
    int d[n];int num=1;
    for(int i=l;i<r+1;i++){
        d[i]=1;
        for(int j=l;j<i;j++){
            if(a[j]<a[i]) {
                d[i]=max(d[i],d[j]+1);
            }
        }
        num=max(num,d[i]);
    }
    for(int i=l;i<r+1;i++) a[i]=d[i];
}
void longestDecrease(int a[],int l,int r){
    int n=r-l+1;
    int d[n];int num=1;
    for(int i=r;i>l-1;i--){
        d[i]=1;
        for(int j=r;j>i;j--){
            if(a[j]<a[i]) d[i]=max(d[i],d[j]+1);
        }
        num=max(num,d[i]);
    }
    for(int i=l;i<r+1;i++) a[i]=d[i];
}

int main() {
    int n;
    while(cin>>n){
        int a[n];
        int dp1[n];
        int dp2[n];
        for(int i=0;i<n;i++){
            scanf("%d",&a[i]);
            dp1[i]=a[i];
            dp2[i]=a[i];
        }
        
        longestIncrease(dp1,0,n-1);
        longestDecrease(dp2,0,n-1);
        int maxh=1;
        for(int i=0;i<n;i++){
            if((dp1[i]+dp2[i])>maxh) maxh=dp1[i]+dp2[i];
        }
        cout<<(n-maxh+1)<<endl;
    }
}