HJ24 合唱队

题目描述

N 位同学站成一排，音乐老师要请最少的同学出列，使得剩下的 K 位同学排成合唱队形。

设K位同学从左到右依次编号为 1，2…，K ，他们的身高分别为T1,T2,…,TK ，若存在i(1≤i≤K) 使得T1<T2<……<Ti−1<Ti 且 Ti>Ti+1>……>TK，则称这K名同学排成了合唱队形。

通俗来说，能找到一个同学，他的两边的同学身高都依次严格降低的队形就是合唱队形。

示例

123 124 125 123 121 是一个合唱队形

123 123 124 122不是合唱队形，因为前两名同学身高相等，不符合要求

123 122 121 122不是合唱队形，因为找不到一个同学，他的两侧同学身高递减。

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

注意：不允许改变队列元素的先后顺序 且 不要求最高同学左右人数必须相等

思路

最长递增子序列：

1. 求出最长递增子序列数组LIS[]，其中LIS[i]表示[1, i]这个区间内最长递增子序列的长度。
2. 求出最长递减子序列数组LDS[]，其中LDS[i]表示[1, i]这个区间内最长递减子序列的长度。
3. for循环遍历[1, n]，（LIS[i] + LDS[i] - 1） 即为最多可留下的人数，找出最大值即可。

我在求LDS时，是把数组翻转过来求LIS，求完了再把结果数组翻转一下就是了。

Code

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int INF = 0x3f3f3f3f;
const int N = 3005;

int a[N];
int b[N];
int low[N];
int LIS[N];
int LDS[N];

void reverseArr(int* arr, int n) {
    for (int i = 1; i <= n / 2; ++i) {
        swap(arr[i], arr[n - i + 1]);
    }
}

void longestIncreasingSubsequence(int* arr, int* L, int n) {
    int idx = 1;
    memset(low, INF, sizeof(low));
    L[1] = idx;
    low[idx] = arr[1];
    for (int i = 2; i <= n; ++i) {
        if (low[idx] < arr[i]) {
            low[++idx] = arr[i];
            L[i] = idx;
        } else {
            int pos = lower_bound(low + 1, low + 1 + idx, arr[i]) - low;
            low[pos] = arr[i];
            L[i] = pos;
        }
    }
}

int main() {
    freopen("00input.txt", "r", stdin);

    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }

        longestIncreasingSubsequence(a, LIS, n);
        reverseArr(a, n);
        longestIncreasingSubsequence(a, LDS, n);
        reverseArr(LDS, n);

        int longest = 0;
        for (int i = 1; i <= n; ++i) {
            longest = max(longest, LIS[i] + LDS[i] - 1);
        }
        cout << n - longest << '\n';
    }

    return 0;
}

算法思想可参考：https://writings.sh/post/longest-increasing-subsequence-revisited