一本通-1264：【例9.8】合唱队形

【题目描述】 N位同学站成一排，音乐老师要请其中的(N−K)位同学出列，使得剩下的KK位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K，他们的身高分别为T1,T2,…,TK，则他们的身高满足T1<T2<…Ti+1>…>TK(1≤i≤K)。

你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。

【输入】 输入的第一行是一个整数N（2≤N≤100），表示同学的总数。第二行有n个整数，用空格分隔，第i个整数Ti（130≤Ti≤230）是第i位同学的身高（厘米）。

【输出】 输出包括一行，这一行只包含一个整数，就是最少需要几位同学出列。

【输入样例】 8 186 186 150 200 160 130 197 220

【输出样例】 4

#include <bits/stdc++.h>

using namespace std;

int n;
vector<int> seq(105), forwardSeq(105), backwardSeq(105);
vector<int> d(105), c(105);

int solve()
{
    forwardSeq[1] = seq[0];
    int len1 = 1;
    d[1] = 1;
    for (int i = 1; i < n; ++i) {
        int target = seq[i];

        int left = 1, right = len1 + 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (forwardSeq[mid] < target) left = mid + 1;
            else right = mid;
        }
        if (left == len1 + 1) {
            forwardSeq[++len1] = target;
            d[i + 1] = len1;
        }
        else {
            forwardSeq[left] = target;
            d[i + 1] = left;
        }
    }

    backwardSeq[1] = seq[n - 1];
    int len2 = 1;
    c[n] = 1;
    for (int i = n - 2; i >= 0; --i) {
        int target = seq[i];

        int left = 1, right = len2 + 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (backwardSeq[mid] < target) left = mid + 1;
            else right = mid;
        }
        if (left == len2 + 1) {
            backwardSeq[++len2] = target;
            c[i + 1] = len2;
        }
        else {
            backwardSeq[left] = target;
            c[i + 1] = left;
        }
    }

    int maxVal = -1;
    for (int i = 1; i <= n; ++i) {
        maxVal = max(maxVal, c[i] + d[i] - 1);
    }

    return n - maxVal;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) cin >> seq[i];
    cout << solve() << endl;

    return 0;
}

第一遍正向遍历，寻找最长上升子序列，用d[i]表示以seq[i - 1]结尾的最长上升子序列长度，第二遍逆序遍历，用c[i]记录以seq[i - 1]结尾的最长上升子序列长度（从后往前看），那么最终形成的先上升后下降的最大长度是d[i] + c[i] - 1，因为第i个人被重复计算了一次。那么最后只需要删掉n - max(d[i] + c[i] - 1)个人即可。