合唱队形

题目描述

$N$ 位同学排成一排，老师想让其中的 $(N-K)$ 位出列，使剩下的 $K$ 位同学身高呈“先严格上升、后严格下降”的合唱队形。给定 $N$ 和各位同学的身高，求最少需要出列的同学数。 $2 \le N \le 100$ ， $130 \le T_i \le 230$ 。

输入第一行为 $N$ ，第二行为 $N$ 个身高；输出一行，为最少出列人数。

样例输入：

text

1
28
186 186 150 200 160 130 197 220

样例输出：

text

思路

以每个位置 $i$ 为峰值，左段是以 $i$ 结尾的最长严格上升子序列 rise[i]，右段等价于把序列反转后求一次同样的严格上升子序列 fall[i]。峰值被算了两次，所以最多保留人数为 $\max_i\big(\text{rise}[i]+\text{fall}[i]-1\big)$ ，答案为 $N$ 减去该值。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 02:25
# update_at: 2026-09-30 02:25

import sys


def lis_heights(nums: list[int]) -> list[int]:
    """以每个位置结尾、严格上升子序列的最大长度（LIS 经典 O(n^2) DP）。"""
    dp: list[int] = []  # dp[i] = 以 nums[i] 结尾的 LIS 长度
    for i, height in enumerate(nums):
        dp.append(1 + max((dp[j] for j in range(i) if nums[j] < height), default=0))
    return dp


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    heights = [next(data) for _ in range(n)]  # 每位同学的身高

    rise = lis_heights(heights)                # rise[i]：i 左侧（含 i）的最长严格上升
    fall = lis_heights(heights[::-1])[::-1]    # fall[i]：i 右侧（含 i）的最长严格下降

    # 峰值算两次，减 1；n<=2 时队列必然不严格，max 兜底为 0，答案输出 n
    keep = max((r + f - 1 for r, f in zip(rise, fall)), default=0)
    print(n - max(keep, 0))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 07:27
 * update_at: 2026-10-05 07:27
 */

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 105;

ll h[MAXN];      // 每位同学的身高
ll rise[MAXN];   // rise[i]：以 i 结尾的最长严格上升子序列长度
ll fall[MAXN];   // fall[i]：从 i 开始的最长严格下降子序列长度

// 对数组 a[1..n] 求以每个位置结尾的最长严格上升子序列长度
void lis_strict(ll a[], ll dp[], ll n) {
    for (ll i = 1; i <= n; i++) {
        dp[i] = 1; // 至少包含自己
        for (ll j = 1; j < i; j++) {
            if (a[j] < a[i] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    ll n;
    cin >> n;
    for (ll i = 1; i <= n; i++) {
        cin >> h[i];
    }

    lis_strict(h, rise, n); // 正向求严格上升

    // 反转序列求“严格上升”，对应原序列的“严格下降”
    ll rev_h[MAXN];
    ll rev_dp[MAXN];
    for (ll i = 1; i <= n; i++) {
        rev_h[i] = h[n - i + 1];
    }
    lis_strict(rev_h, rev_dp, n);
    for (ll i = 1; i <= n; i++) {
        fall[i] = rev_dp[n - i + 1];
    }

    ll keep = 0; // 最多能保留的同学数
    for (ll i = 1; i <= n; i++) {
        ll total = rise[i] + fall[i] - 1; // 峰值被算了两次，减 1
        if (total > keep) {
            keep = total;
        }
    }

    cout << n - keep << "\n";
    return 0;
}

目录

题目描述

思路

参考代码