题解 | 合唱队

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> heights(n);
    for (int i = 0; i < n; ++i) {
        cin >> heights[i];
    }

    // 计算以每个同学为结尾的最长递增子序列长度
    vector<int> dp_increase(n, 1);
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (heights[i] > heights[j]) {
                dp_increase[i] = max(dp_increase[i], dp_increase[j] + 1);
            }
        }
    }

    // 计算以每个同学为开头的最长递减子序列长度
    vector<int> dp_decrease(n, 1);
    for (int i = n - 1; i >= 0; --i) {
        for (int j = n - 1; j > i; --j) {
            if (heights[i] > heights[j]) {
                dp_decrease[i] = max(dp_decrease[i], dp_decrease[j] + 1);
            }
        }
    }

    // 找出能构成合唱队形的最大人数
    int max_people = 0;
    for (int i = 0; i < n; ++i) {
        // 注意这里要减去 1，因为当前同学被重复计算了一次
        max_people = max(max_people, dp_increase[i] + dp_decrease[i] - 1);
    }

    // 计算最少需要出列的同学数量
    int min_out = n - max_people;

    cout << min_out << endl;

    return 0;
}