题解 | #合唱队#

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

int main(){
      /*
        最少出队 == 队伍里剩下的人数最多
        队伍要求，山峰状，即从左到顶峰是一个最长递增子序列，从右到顶峰是一个最长递增子序列
        将问题转换成求2次最长递增子序列
        dp1[i] 表示从左往右，以i为结尾的最长子序列长度
        dp2[i] 表示从右往左，以i为结尾的最长子序列长度
        dp1[i] + dp2[i] - 1 表示以i为峰值的队伍长度（峰值算了2次，因此要-1）
        最优解出现在 max(dp1[i] + dp2[i] - 1 )
      */
    int n;
    cin >> n;
    vector<int> heights(n);
    for(int i = 0 ; i < n ; i++)
        cin >> heights[i];
    vector<int> dp1(n,1);
    vector<int> dp2(n,1);
    int res = 0;

    //从左到右递增的最长序列
    for(int i = 1 ; i < n ; i++){
        for(int j = 0; j < i ; j++){
            if( heights[i] > heights[j] )
                dp1[i] = max(dp1[i],dp1[j]+1);
        }
    }

    // 从右到左递增的最长序列
    for(int i = n -2 ; i >= 0 ; i--){
        for(int j = n - 1 ;  j > i ; j--){
            if( heights[i] > heights[j] )
                dp2[i] = max(dp2[i],dp2[j] + 1);
        }
    }

    for(int i = 0 ; i < n ; i++)
        res = max(res, dp1[i]+dp2[i]-1);

    cout << n - res;
}