[NOIP2004-提高] 合唱队形

题目描述

$N$ 位同学站成一排，删去若干人后使剩余身高满足先严格上升至峰、再严格下降。求最少出列人数。

输入：第一行整数 $N(2\le N\le100)$ ，第二行 $N$ 个整数 $T_i(130\le T_i\le230)$ 。输出：一个整数。

样例：输入 8 与 186 186 150 200 160 130 197 220，输出 4。

思路

枚举峰 $i$ ，以 $i$ 结尾的最长严格上升长度 $up_i$ 与以 $i$ 开头的最长严格下降长度 $down_i$ 拼接，峰被算两次需减 $1$ ；答案 $=N-\max_i(up_i+down_i-1)$ 。

参考代码

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#!/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-10-02 05:52
# update_at: 2026-10-02 05:55

import sys


def lis_ends(h: list[int]) -> list[int]:
    """ends[k] = 以第 k 位结尾的最长严格上升子序列长度（O(N^2) DP）。"""
    ends: list[int] = []
    for i, x in enumerate(h):
        best = max((ends[j] for j in range(i) if h[j] < x), default=0)  # 前面能接上的最长段
        ends.append(best + 1)
    return ends


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    h = [next(data) for _ in range(n)]  # 题面的高度序列
    up = lis_ends(h)                              # 以 i 结尾的严格上升段
    down = lis_ends(h[::-1])[::-1]                # 以 i 开始的严格下降段（反转即上升）
    # 以 i 为峰：上升段和下降段各算一次 i，山峰总长 = up[i] + down[i] - 1
    print(n - max(a + b - 1 for a, b in zip(up, down)))


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/**
 * 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-06 13:28
 * update_at: 2026-10-06 13:28
 */

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

typedef long long ll;

const int MAXN = 105;

ll h[MAXN];      // 身高序列
ll up[MAXN];     // 以 i 结尾的最长严格上升子序列长度
ll down[MAXN];   // 以 i 开头的最长严格下降子序列长度

// 计算以每个位置结尾的最长严格上升子序列长度
void lis_ends(ll a[], ll dp[], int n) {
    for (int i = 1; i <= n; i++) {
        dp[i] = 1; // 至少包含自己
        for (int 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);

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

    lis_ends(h, up, n); // 正向：以 i 结尾的严格上升

    // 反向求下降：把序列反转后求以每个位置结尾的上升，再反转回来
    ll rev_h[MAXN], rev_dp[MAXN];
    for (int i = 1; i <= n; i++) {
        rev_h[i] = h[n - i + 1];
    }
    lis_ends(rev_h, rev_dp, n);
    for (int i = 1; i <= n; i++) {
        down[i] = rev_dp[n - i + 1];
    }

    ll best = 0;
    for (int i = 1; i <= n; i++) {
        best = max(best, up[i] + down[i] - 1);
    }
    cout << n - best << "\n";
    return 0;
}

[NOIP2004-提高] 合唱队形

目录

题目描述

思路

参考代码