题解 | #合唱队#

使用动态规划的思想，对于每一个同学，建立他的左子队和右子队，左子队的人员数目为左边每个身高比他小的人的左子队人员数目中的最大值加一，右子队同理。需要出队的最少人数即为总人数减去最大的队伍人数。

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

int main() {
    int height;
    int n;
    vector<int> list;
    int min = 0;
    int count = 0;
    cin >> n;
    while (cin >> height) {
        list.push_back(height);
    }
    int leftTeam[n];
    int rightTeam[n];
    leftTeam[0] = 1;
    rightTeam[0] = 1;
    int max_num = 1;
    for (int i = 1; i < n; i++) {
        leftTeam[i] = 1;
        rightTeam[i] = 1;
        for (int j = 0; j < i; j++) {
            if (list[i] > list[j]) {
                leftTeam[i] = max(leftTeam[i], leftTeam[j] + 1);
            }
            if (list[n - 1 - i] > list[n - 1 - j]) {
                rightTeam[i] = max(rightTeam[i], rightTeam[j] + 1);
            }
        }
    }
    for (int i = 0; i < n; i++) {
        max_num = max(leftTeam[i] + rightTeam[n - 1 - i] - 1, max_num);
    }
    cout << n - max_num;
}
// 64 位输出请用 printf("%lld")