解题思路

合唱队形要求身高先上升再下降（中间最高）。要让剩下的同学能排成合唱队形，问最少出列几人。

换一种说法：找一条最长的先升后降子序列，剩下的就是出列的。

思路：最长上升子序列 + 最长下降子序列。

1. dp1[i]：从左往右，以第 i 个同学为结尾的最长上升子序列长度
   • 枚举 j < i，如果 a[j] < a[i]，dp1[i] = max(dp1[i], dp1[j]+1)
2. dp2[i]：从右往左，以第 i 个同学为开头的最长下降子序列长度
   • 枚举 j > i，如果 a[j] < a[i]，dp2[i] = max(dp2[i], dp2[j]+1)
3. 以第 i 个同学为最高点的合唱队形人数 = dp1[i] + dp2[i] - 1（i 被算了两次减掉）
4. 取所有 i 的最大值 ma，出列人数 = n - ma

为什么这样能行？ 合唱队形以某个人为最高点，左边的人必须递增，右边的人必须递减。dp1 管左边递增，dp2 管右边递减，拼起来就是以这个人为中心的合唱队形。

注意：a[0] 和 a[n+1] 要当成极小值 0，让每个同学至少能形成长度 1 的序列。

参考代码

#include <iostream>
using namespace std;

int a[105];  // 全局数组自动清零

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

    int dp1[105] = {0}, dp2[105] = {0};

    // 从左到 i 的最长上升子序列
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i]) {
                if (dp1[j] + 1 > dp1[i]) dp1[i] = dp1[j] + 1;
            }
        }
    }

    // 从 i 到右的最长下降子序列
    int ma = -1;
    for (int i = n; i >= 0; i--) {
        for (int j = n + 1; j > i; j--) {
            if (a[j] < a[i]) {
                if (dp2[j] + 1 > dp2[i]) dp2[i] = dp2[j] + 1;
            }
        }
        // 以 i 为最高点的合唱队形人数
        for (int j = 1; j <= n; j++) {
            if (dp1[j] + dp2[j] - 1 > ma) ma = dp1[j] + dp2[j] - 1;
        }
    }

    cout << n - ma;  // 出列人数
    return 0;
}

复杂度分析

• 时间复杂度：O(N²)，两遍最长子序列
• 空间复杂度：O(N)