题解 | #合唱队#

#include <iostream>
#include <vector>
using namespace std;
/*
解题思路：
可看成求每个数的左最长递增序列和右最长递减序列，得到每个位置的左最长递增+右最长递减，取最大值-1即为符合合唱队身高序列人数max
-1是左最长+右最长 自己的位置加了2次  用总人数n - max 即为所求
参考算法笔记中最长不下降子序列(LIS)问题，将判断条件等号去掉即为最长递增序列
求递减序列时需倒着求
*/
int main() {
    int n;
    while(cin >> n){
        vector<int> vi(n+1,0);
        for(int i = 1; i <= n; i++){
            cin >> vi[i];
        }
        vector<int> num1(n+1,0);//左递增最长序列长度
        vector<int> dp1(n+1,1);//dp1[i]表示以vi[i]结尾的最长递增子序列的长度
        
        for(int i = 1; i <= n; i++){
            for(int j = 1; j < i; j++){
                if(vi[i] > vi[j] && dp1[j] + 1 > dp1[i]){//当第i位的身高高于前j位时，且缀在以A[j]结尾后比当前更长
                    dp1[i] = dp1[j] + 1;//子序列长度+1
                }
            }
            num1[i] = max(num1[i],dp1[i]);
        }
        vector<int> num2(n+1,0);//右递减最长子序列长度
        vector<int> dp2(n+1,1);//dp2[i]表示以vi[i]开头的最长递减子序列的长度
         for(int i = n; i >= 1; i--){
            for(int j = n; j > i; j--){
                if(vi[i] > vi[j] && dp2[j] + 1 >dp2[i]){//当第i位身高高于后j位身高时，，且缀在以A[j]开头前比当前更长
                    dp2[i] = dp2[j] + 1;//子序列长度+1
                }
            }
            num2[i] = max(num2[i],dp2[i]);
        }
        int max = 0;
        for(int i = 1; i <= n; i++){
            if(max < num1[i] + num2[i])
                max = num1[i] + num2[i];//找出最长子序列长度和
        }
        cout << n - max + 1 << endl;
    }
}
// 64 位输出请用 printf("%lld")