P1091 [NOIP 2004 提高组] 合唱队形

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> t(n);
    for (int &x : t) cin >> x;

    // up[i]：以第 i 位同学结尾的最长上升子序列长度
    // down[i]：以第 i 位同学开头的最长下降子序列长度
    vector<int> up(n, 1), down(n, 1);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < i; j++)
            if (t[j] < t[i]) up[i] = max(up[i], up[j] + 1);

    for (int i = n - 1; i >= 0; i--)
        for (int j = i + 1; j < n; j++)
            if (t[j] < t[i]) down[i] = max(down[i], down[j] + 1);

    // 第 i 位同学当队形的最高点时，最多能留下 up[i] + down[i] - 1 人
    int best = 0;
    for (int i = 0; i < n; i++) best = max(best, up[i] + down[i] - 1);

    cout << n - best << "\n";
    return 0;
}