题解 | #合唱队#

#include <iostream>
using namespace std;
#include <bits/stdc++.h>
int main() {
    int n;
    cin>>n;
    vector<int>heights(n);
    for(int i = 0; i < n; i++){
        cin>>heights[i];
    }
    vector<int>dp1(n,1),dp2(n,0);
    for(int i = 1; i < n; i++){
        for(int j = 0; j < i; j++){
            if(heights[j] < heights[i]){
                dp1[i] = max(dp1[j]+1,dp1[i]);
            }
        }
    }
    for(int i = n - 2; i >= 0; i--){
        for(int j = n - 1; j > i; j--){
            if(heights[j] < heights[i]){
                dp2[i] = max(dp2[j]+1,dp2[i]);
            }
        }
    }
    int MAX =INT_MIN;
    for(int i = 0; i < n; i++){
        dp1[i] += dp2[i];
        MAX = max(MAX,dp1[i]);
    }
    cout<<n-MAX<<endl;
    return 0;
}
// 64 位输出请用 printf("%lld")