题解 | 合唱队形

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

int main() {
    int num;
    while (cin >> num) {
        vector<int> stu(num);
        for (int i = 0; i < num; i++)
            cin >> stu[i];
        vector<int> add(num, 1); // 前i个元素的最长递增子序列的长度
        for (int i = 1; i < num; i++)
            for (int j = i; j >= 0; j--)
                if (stu[j] < stu[i])
                    add[i] = max(add[i], add[j] + 1);
        vector<int> reduce(num, 1); // 后i个元素的最长递减子序列的长度
        for (int i = num - 1; i >= 0; i--)
            for (int j = i; j < num; j++)
                if (stu[j] < stu[i])
                    reduce[i] = max(reduce[j] + 1, reduce[i]);
        int k = 0; // 剩下K位同学
        for (int i = 0; i < num; i++)
            k = max(k, (add[i] + reduce[i]) - 1);
        cout << num - k << endl;
    }
    return 0;
}