洛谷-P1091 合唱队形（LIS）

题目描述

N*N*位同学站成一排，音乐老师要请其中的(N-K*N*−K)位同学出列，使得剩下的K*K*位同学排成合唱队形。

合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1,2,…,K1,2,…,K，他们的身高分别为T_1,T_2,…,T_K*T*1,T*2,…,*T**K， 则他们的身高满足T_1<...T_{i+1}>…>T_K(1 \le i \le K)T*1<...<*T**i>T**i+1>…>T**K(1≤i≤K)。

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

输入格式

共二行。

第一行是一个整数N(2 \le N \le 100)N(2≤N≤100)，表示同学的总数。

第二行有n*n*个整数，用空格分隔，第i*i*个整数T_i(130 \le T_i \le 230)T**i(130≤T**i≤230)是第i*i*位同学的身高(厘米)。

输出格式

一个整数，最少需要几位同学出列。

输入输出样例

输入 #1

8
186 186 150 200 160 130 197 220

输出 #1

4

说明/提示

对于50％的数据，保证有n \le 20*n*≤20；

对于全部的数据，保证有n \le 100*n*≤100。

---

#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)个人即可。