题解 | 合唱队

#include <iostream>

using namespace std;
#define N 3010
int up[N];
int down[N];
int a[N];
int n;

void init() {
    for (int i = 1; i <= n; ++i) up[i] = down[i] = 1;
}

void dp() {
    // 计算最长上升子序列
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j < i; ++j)
            if (a[i] > a[j])
                up[i] = max(up[i], up[j] + 1);
    // 计算最长下降子序列
    for (int i = n; i >= 1; --i)
        for (int j = n; j > i; --j)
            if (a[i] > a[j])
                down[i] = max(down[i], down[j] + 1);
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i)
        scanf("%d", &a[i]);
    init();
    dp();
    int max_k = 0;
    for (int i = 1; i <= n; ++i)
        max_k = max(max_k, up[i] + down[i] - 1);
    cout << n - max_k << endl;

    return 0;
}