题解 | #[NOIP2004]合唱队形#

#include<iostream>
using namespace std;
const int N=110;
int a[N],f1[N],f2[N],n;
int main(){
    cin>>n;
    for(int i=0;i<n;i++)cin>>a[i];
    for(int i=1;i<n;i++)
        for(int j=0;j<=i;j++)
        if(a[j]<a[i])f1[i]=max(f1[i],f1[j]+1);
            
    for(int i=n-2;i>=0;i--)
        for(int j=i+1;j<n;j++)
        if(a[j]<a[i])f2[i]=max(f2[i],f2[j]+1);
    
    int ans=0;
     for(int i=0;i<n;i++)
         ans=max(ans,f1[i]+f2[i]+1);
    
    cout<<n-ans;
    
    
    
    
    return 0;
}