题解 | #合唱队#

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int stu_num;
    cin>>stu_num;
    vector<int> height(stu_num,0);
    for (int i=0; i<stu_num; i++) {
        cin>>height[i];
    }

    vector<int> dp1(stu_num,1);
    vector<int> dp2(stu_num,1);

    
    for (int i=1; i<stu_num; i++) {
        for (int j=0; j<i; j++) {
        if (height[j]<height[i]) {
        dp1[i]=max(dp1[i],dp1[j]+1);
        }
        }
    }

    for (int i=stu_num-2; i>=0; i--) {
        for (int j=stu_num-1; j>i; j--) {
            if (height[j]<height[i]){
            dp2[i]=max(dp2[i],dp2[j]+1);
            }
        }
    }

    int result=0;
    for (int i=0; i<stu_num; i++) {
        //cout<<dp1[i]<<' '<<dp2[i]<<endl;
        result=max(result,dp1[i]+dp2[i]-1);
    }
    result=stu_num-result;
    cout<<result<<endl;
    
}
// 64 位输出请用 printf("%lld")