合唱

题目

合唱队不允许有人摸鱼！

小J和小R在计算机合唱队准备排练，他们将要登上舞台准备表演。

这一次他们想要站成两端高中间低的队列，现在他们已经站成了一排，小J和小R想知道出去最少多少人过后他们可以让队列形成两端高中间低。

所有同学排成了一排，每个人都有一个身高值，求最少多少人离队后可以让队伍形成两头高中间低的形状。注意指的是身高严格高低变化，也就是前半段每一位同学身高都大于下一个人，后半段每一位同学身高都小于下一个人，不包含相等的情况。（可以没有前半段或者后半段）

输入：第一行一个整数 N，表示队伍人数。第二行 N 个整数表示每个人的身高。
输出：一个整数，表示最少离开多少人后队伍可以形成严格的两头高中间低的形状。

样例1：

5
1 2 1 3 5

1

样例2：

6
5 4 5 2 3 6

1

提示：对于 30% 的数据，保证 N≤10。对于 70% 的数据，保证 N≤100。对于 100% 的数据，保证 N≤1000。

思路

最少赶走几人 = N − 最多能留几人。枚举每个位置 i 作为谷底：用 f[i] 记录以 i 结尾的最长严格递减子序列长度（左坡），用 g[i] 记录以 i 开头的最长严格递增子序列长度（右坡）。以 i 为谷底最多可留 f[i]+g[i]−1 人，取所有谷底的最大值即可。g[i] 只需从右往左遍历，就变成了和 f[i] 完全对称的经典 LIS 问题。

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

int main() {
    int N;
    cin >> N;
    vector<int> a(N);
    for (int i = 0; i < N; ++i)
        cin >> a[i];

    // f[i] 表示以 i 结尾的最长严格递减子序列长度
    vector<int> f(N, 1);
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < i; ++j)
            if (a[j] > a[i])
                f[i] = max(f[i], f[j] + 1);

    // g[i] 表示以 i 开始的最长严格递增子序列长度（从右往左遍历）
    vector<int> g(N, 1);
    for (int i = N - 1; i >= 0; --i)
        for (int j = i + 1; j < N; ++j)
            if (a[j] > a[i])
                g[i] = max(g[i], g[j] + 1);

    int max_len = 0;
    for (int i = 0; i < N; ++i)
        max_len = max(max_len, f[i] + g[i] - 1);

    cout << N - max_len << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(N²)，f 和 g 各一次双重循环
• 空间复杂度：O(N)，f、g 两个数组

← 返回菜鸟的coding