简单

问题分析
本题的目标是计算最少需要让多少位同学出列，使得剩下的同学能够排成合唱队形。合唱队形的特点是存在一个最高点，从左到右身高先递增，到最高点后身高再递减。

算法思路
可以通过计算以每个同学为最高点时，其左边的最长递增子序列（LIS）长度和右边的最长递减子序列（LDS）长度，然后找出所有可能情况下的最长合唱队形长度，最后用总人数减去最长合唱队形长度，即可得到最少出列人数。

#include <iostream> 
#include <vector> 
#include <algorithm> 
 
using namespace std; 
 
// 计算最长递增子序列的长度 
int LIS(const vector<int>& arr) { 
    int n = arr.size();  
    vector<int> dp(n, 1); 
    for (int i = 0; i < n; ++i) { 
        for (int j = 0; j < i; ++j) { 
            if (arr[j] < arr[i]) { 
                dp[i] = max(dp[i], dp[j] + 1); 
            } 
        } 
    } 
    return *max_element(dp.begin(),  dp.end());  
} 
 
// 计算最长递减子序列的长度 
int LDS(const vector<int>& arr) { 
    int n = arr.size();  
    vector<int> dp(n, 1); 
    for (int i = 0; i < n; ++i) { 
        for (int j = 0; j < i; ++j) { 
            if (arr[j] > arr[i]) { 
                dp[i] = max(dp[i], dp[j] + 1); 
            } 
        } 
    } 
    return *max_element(dp.begin(),  dp.end());  
} 
 
int main() { 
    int n; 
    cin >> n; 
    vector<int> heights(n); 
    for (int i = 0; i < n; ++i) { 
        cin >> heights[i]; 
    } 
 
    int maxChorusLength = 0; 
    // 枚举每个同学作为最高点 
    for (int i = 0; i < n; ++i) { 
        // 计算左边的最长递增子序列 
        vector<int> left(heights.begin(),  heights.begin()  + i + 1); 
        int leftLIS = LIS(left); 
 
        // 计算右边的最长递减子序列 
        vector<int> right(heights.begin()  + i, heights.end());  
        int rightLDS = LDS(right); 
 
        // 最长合唱队形长度为左边LIS长度加上右边LDS长度再减去重复计算的最高点 
        maxChorusLength = max(maxChorusLength, leftLIS + rightLDS - 1); 
    } 
 
    // 最少出列人数为总人数减去最长合唱队形长度 
    int minOut = n - maxChorusLength; 
    cout << minOut << endl; 
 
    return 0; 
} 

代码解释
LIS函数：用于计算最长递增子序列的长度。通过动态规划的方法，维护一个dp数组，dp[i]表示以第i个元素结尾的最长递增子序列的长度。
LDS函数：用于计算最长递减子序列的长度。与LIS函数类似，只是比较条件变为arr[j] > arr[i]。
主函数：
读取输入的总人数n和每个同学的身高。
枚举每个同学作为最高点，分别计算其左边的最长递增子序列长度和右边的最长递减子序列长度。
计算最长合唱队形长度，取所有可能情况下的最大值。
最少出列人数为总人数减去最长合唱队形长度。
复杂度分析
时间复杂度：O(n2)，主要是由于计算LIS和LDS时需要两层嵌套循环。
空间复杂度：O(n)，主要用于存储dp数组。
记得点个赞