题解 | #合唱队#

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

int main(int argc, char* argv[]){
    int N;
    cin >> N;
    vector<int> heights(N, 0);
    for(int i = 0; i < N; ++i){
        cin >> heights[i];
    }
    //dp_up[i]表示从heights[0]到heights[i]最长递增子序列的长度
    vector<int> dp_up(N, 1);
    dp_up[0] = 1;
    for(int i = 1; i < N; ++i){
        for(int j = 0; j < i; ++j){
            if(heights[i] > heights[j]){
                dp_up[i] = max(dp_up[i], dp_up[j]+1);
            }
        }
    }
    //dp_down[i]表示heights[i]到heights[N-1]最长递减子序列的长度
    vector<int> dp_down(N, 1);
    dp_down[N-1] = 1;
    for(int i = N-2; i >= 0; --i){
        for(int j = N-1; j > i; --j){
            if(heights[i] > heights[j]){
                dp_down[i] = max(dp_down[i], dp_down[j]+1);
            }
        }
    }

    int maxLength = 0;
    for(int i = 0; i < N; ++i){
        maxLength = max(maxLength, dp_up[i]+dp_down[i]-1);
    }
    cout << N-maxLength << endl;
    return 0;
}