题解 | #合唱队#

本质是两个最长递增子序列问题

#include "vector"
#include "algorithm"

using namespace std;

int main(){
    int N = 0;
    cin >> N;
    vector<int> height(N, 0);
    for(int i = 0; i < N; ++i){
        cin >> height[i];
    }
    vector<int> dp1(N);
    vector<int> dp2(N);
    dp1[0] = 1;
    for(int i = 1; i < N; ++i){
        dp1[i] = 1;
        for(int j = 0; j < i; ++j){
           if(height[i] > height[j]) dp1[i] = max(dp1[i], dp1[j] + 1); 
        }
    }
    dp2[0] = 1;
    reverse(height.begin(), height.end());
    for(int i = 1; i < N; ++i){
        dp2[i] = 1;
        for(int j = 0; j < i; ++j){
           if(height[i] > height[j]) dp2[i] = max(dp2[i], dp2[j] + 1); 
        }
    }
    reverse(dp2.begin(),dp2.end());
    int ans = 0;
    for(int i = 0; i < N; ++i){
        ans = max(dp1[i] + dp2[i] - 1, ans);
    }
    cout << N - ans << endl;
    return 0;
}