合唱队形问题：最小出列人数

链接：https://ac.nowcoder.com/acm/contest/24213/1011
来源：牛客网

题目描述

N位学生站成一排，音乐老师需要请其中的(N-K)位学生离开，以使剩下的K位学生形成合唱队形。

合唱队形定义如下：设K位学生从左到右依次编号为1, 2, ..., K，他们的身高分别为T₁, T₂, ..., T_K，则他们的身高满足T₁ <... i > T_i+1 > ... > T_K (1 <= i <= K)。

你的任务是，已知所有N位学生的身高，计算最少需要几位学生离开，以使剩下的学生形成合唱队形。

输入描述:

输入的第一行是一个整数N (2 <= N <= 100)，表示学生的总数。第二行有N个整数，用空格分隔，第i个整数T_i (130 <= T_i <= 230) 是第i位学生的身高（厘米）。

输出描述:

输出包括一行，这一行只包含一个整数，表示最少需要几位学生离开。

示例1

输入：
8
186 186 150 200 160 130 197 220

输出：
4

备注:

对于50%的数据，保证有N <= 20；
对于全部的数据，保证有N <= 100。

分析

为了找到最少需要离开的学生数量，我们需要从左到右和从右到左分别求出每个位置的最大递增子序列长度。具体步骤如下：

• 从左到右遍历，计算每个位置的最大递增子序列长度，记为p[i]。
• 从右到左遍历，计算每个位置的最大递增子序列长度，记为q[i]。
• 对于每个位置i，计算p[i] + q[i] - 1（因为p[i]和q[i]在i位置重复计算了一次），取最大值mx。
• 最终结果为N - mx。

注意：在计算过程中，确保不要遗漏任何边界条件。

代码实现

#include 
#include 
using namespace std;

const int N = 105;
int n;
int a[N], p[N], q[N];

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

    // 从左到右计算最大递增子序列
    for (int i = 1; i <= n; i++) {
        p[i] = 1;
        for (int j = 1; j  a[j]) {
                p[i] = max(p[i], p[j] + 1);
            }
        }
    }

    // 从右到左计算最大递增子序列
    for (int i = n; i >= 1; i--) {
        q[i] = 1;
        for (int j = n; j > i; j--) {
            if (a[i] > a[j]) {
                q[i] = max(q[i], q[j] + 1);
            }
        }
    }

    int mx = 0;
    for (int i = 1; i <= n; i++) {
        mx = max(mx, p[i] + q[i] - 1);
    }

    cout <