题解 | 合唱队形

#include <bits/stdc++.h>
using namespace std;
const int N  =2000;
int a[N],f[N],f2[N];
int main() {
    int n ;
    cin>>n;
    for(int i = 1; i <= n; i++){
        cin>>a[i];
        for(int j = 1; j < i; j++){
            if(a[i] > a[j]) f[i]  = max(f[i], f[j]);
            
        }
        f[i]++;

    }
    for(int i = n; i >= 1; i--){
        for(int j = n; j > i; j--){
            if(a[i] > a[j]) f2[i]  = max(f2[i], f2[j]);
        }
        f2[i]++;
    }
    int mx = 0;
    for(int i = 1; i <= n; i++){
        int cnt = f[i]+f2[i]-1;
        mx = max(cnt,mx);
    }
    cout<<n-mx;
}