题解 | #合唱队#

#include <bits/stdc++.h>
using namespace std;

const int N=3010;

array<int,N>up,a,down;
int n;

int main() {
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];

    for(int i=1;i<=n;i++){
        up[i]=1;
        for(int j=1;j<i;j++){
            if(a[j]<a[i])
                up[i]=max(up[j]+1,up[i]);
        }
    }
    for(int i=n;i>=1;i--){
        down[i]=1;
        for(int j=i+1;j<=n;j++){
            if(a[j]<a[i])
                down[i]=max(down[j]+1,down[i]);
        }
    }
    int res=max(up[n],down[1]);
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            res=max(res,up[i]+down[j]);
    cout<<n-res<<endl;;
    return 0;
}
// 64 位输出请用 printf("%lld")