题解 | #合唱队形#

最长【先递增后递减子序列】

#include <iostream>
using namespace std;


//合唱队形
int num[110];
int inde[110];
int dp[110];

int maxincrease(int n){
    for(int i=0;i<110;i++)inde[i]=0;
    inde[0]=1;
    for(int i=1;i<=n;i++){
        inde[i]=1;
        for(int j=0;j<i;j++){
            if(num[j]<num[i])
                inde[i]=max(inde[i],inde[j]+1);
        }
    }
    return inde[n];
}

int maxdecrease(int k,int n){
    for(int i=0;i<110;i++)inde[i]=0;
    inde[n-1]=1;
    for(int i=n-2;i>=k;i--){
        inde[i]=1;
        for(int j=n-1;j>i;j--){
            if(num[j]<num[i])
                inde[i]=max(inde[i],inde[j]+1);
        }
    }
    return inde[k];
}

int maxinde(int n){
    int ans=0;
    for(int i=0;i<n;i++){
      dp[i]=maxincrease(i)+maxdecrease(i,n)-1;
      ans=max(dp[i],ans);
    }
    return n-ans;
}

int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>num[i];
    }
    int ans=maxinde(n);
    cout<<ans<<endl;
    return 0;
}