[HNOI2010] 合唱队

形式化题目

给定长度为 $n$ 的数列 $h_1, h_2, \dots, h_n$ ，其中元素两两不同，代表理想队形从左到右的身高。

考虑 $h$ 的任意一个排列 $p_1, p_2, \dots, p_n$ （代表初始站队顺序）。从空序列开始依次处理 $p_k$ ：

$k = 1$ 时直接把 $p_1$ 放入序列；
$k \geqslant 2$ 时，若 $p_k > p_{k-1}$ 就放到当前序列最右端，否则放到最左端。

求有多少个排列 $p$ 最终得到序列恰好是 $h_1, \dots, h_n$ ，答案对 $19650827$ 取模。数据范围 $n \leqslant 1000$ ， $1000 \leqslant h_i \leqslant 2000$ 。

注意规则里“和前一个人比”比的是上一位插入的人，不是队形里相邻的某个人。

暴力解法

思路

题意已经把过程写得很清楚，最直接的做法就是照着走：先决定第一个站出来的人是谁，然后一步步决定后面每个人往哪边插。

关键在于每一步只有两种可能。假设当前队形已经占了理想队形的某个连续段 $[l, r]$ ，那么下一位被插入的人只可能是段外的 $h_{l-1}$ 或 $h_{r+1}$ ：

想插到左端，就必须满足 $h_{l-1} < \text{(最后插入者的身高)}$ ，因为只有更矮的人才会被放到最左边；
想插到右端，就必须满足 $h_{r+1} > \text{(最后插入者的身高)}$ 。

于是 brute.cpp 的 dfs(l, r, last_idx) 表示“已构成区间 $[l, r]$ 、最后插入的人是 last_idx”，逐层尝试这两种扩张，走到 $[1, n]$ 就记一种完整方案；外层再枚举第一个出发点 $i$ ，把 dfs(i, i, i) 累加起来。

这个搜索覆盖了全部合法方案，因此小数据下的答案一定正确，正好用来对拍。

代码

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/**
 * 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-23 23:13
 * update_at: 2026-10-23 23:13
 */
#include <bits/stdc++.h>
using namespace std;

const int MOD = 19650827;

static int n;
static vector<int> h; // h[i]：理想队形中第 i 个人的身高（下标从 1 开始）

// dfs：当前已构成目标区间 [l, r]，最后插入的人是 last_idx，返回扩满 [1, n] 的方案数。
// 只适合小数据：同一个 (l, r, last_idx) 会被不同路径反复访问，指数级重复计算。
int dfs(int l, int r, int last_idx) {
    if (l == 1 && r == n) {
        return 1;
    }

    long long ways = 0;

    if (l > 1 && h[l - 1] < h[last_idx]) {
        ways += dfs(l - 1, r, l - 1);
    }
    if (r < n && h[r + 1] > h[last_idx]) {
        ways += dfs(l, r + 1, r + 1);
    }

    return ways % MOD;
}

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

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

    long long ans = 0;
    for (int i = 1; i <= n; ++i) {
        // 暴力枚举第一个站出来的人是谁，再直接搜索后续扩展区间的方式。
        ans += dfs(i, i, i);
    }

    cout << ans % MOD << '\n';
    return 0;
}

复杂度

外层枚举 $n$ 个起点，每次搜索最多走 $n$ 层、每层 2 个分支，最坏 $O(2^n)$ 条路径，每条路径 $O(n)$ 累计，总时间复杂度 $O(n \cdot 2^n)$ ；空间复杂度 $O(n)$ （递归栈）。

瓶颈

瓶颈是同一个状态被反复算了很多遍。不同路径经常收敛到同一个 $(l, r, last\_idx)$ ，而这三元组一旦确定，后面能产生多少种方案就是固定的。但上面的搜索每次遇到它都要重新展开一遍，于是指数爆炸： $n = 20$ 就已经算不动，而题目要求 $n \leqslant 1000$ 。

把“算过的答案记下来”就得到记忆化搜索，进一步发现状态本来就是由区间长度一层层推上去的，写成从短区间到长区间的递推即可——这就是下面的正解。

正解

关键观察

倒过来看插入过程。每次新来的人只会被放到当前队形的最左端或最右端，所以已经入队的那些人，在理想队形里一定占据连续的一段 $[l, r]$ 。而且这不只是巧合：只要这一段确定了，能插进来的人就只能是 $h_{l-1}$ 与 $h_{r+1}$ 之一。

第二个观察是：规则里要比的“前一个人”就是最后插入的那个人，而最后插入的人一定站在区间两端之一。所以“谁最后进去”只有两种可能：左端 $h_l$ 或右端 $h_r$ 。

这两点合起来，状态就有了：

dp_{l,r,0} = \text{已构成 } [l,r] \text{、且最后插入的是左端 } h_l \text{ 的方案数},\qquad dp_{l,r,1} = \text{最后插入的是右端 } h_r \text{ 的方案数}.

其中 $0$ 与 $1$ 两个值不重复计数：它们是“最后一步插在哪边”的两种不同情况。

思路

初始化：任意单点区间都能作为起点，令 $dp_{i,i,0} = 1$ ， $dp_{i,i,1} = 0$ 。

单点只记一个方向，是因为 $n = 1$ 时长度为 $1$ 的状态本身就对应一种初始队形；两个方向都置 $1$ 会把答案翻倍。

转移按区间长度从小到大做。长度 $1$ 的区间已经确定，长度 $\mathit{len}$ 的区间只由长度 $\mathit{len}-1$ 的区间推出来，所以外层枚举 $\mathit{len}$ 从 $2$ 到 $n$ 。

以新状态 $dp_{l,r,0}$ （最后插入的是左端 $h_l$ ）为例，它只能由“少一个左端点”的区间 $[l+1, r]$ 扩张而来，此时扩张的人正是 $h_l$ ，要比的是 $[l+1,r]$ 的最后插入者：

若 $[l+1,r]$ 最后插入的是左端 $h_{l+1}$ ： $h_l$ 要插到左边，需要 $h_l < h_{l+1}$ ；
若 $[l+1,r]$ 最后插入的是右端 $h_r$ ：需要 $h_l < h_r$ 。

dp_{l,r,0} = [\,h_l < h_{l+1}\,]\, dp_{l+1,r,0} + [\,h_l < h_r\,]\, dp_{l+1,r,1}

对称地， $dp_{l,r,1}$ 由 $[l, r-1]$ 扩张而来，扩张的人是 $h_r$ ，需要比 $h_l$ 或 $h_{r-1}$ 更高：

dp_{l,r,1} = [\,h_r > h_l\,]\, dp_{l,r-1,0} + [\,h_r > h_{r-1}\,]\, dp_{l,r-1,1}

（ $[\cdot]$ 表示条件成立取 $1$ 、否则取 $0$ 。）main.cpp 写成从 $[l,r]$ 往两边“推”的形式，与上面从两侧“拉”的形式完全等价；对应的“拉”式实现见下文的「写法变体」小节。

答案：起点可以是任意一个人，所以把所有情形都汇到 $[1, n]$ 再求和：

ans = \left(dp_{1,n,0} + dp_{1,n,1}\right) \bmod 19650827

因为 $n=1$ 时只有 $dp_{1,1,0}=1$ ，这个式子也直接给出正确答案 $1$ 。

下面用样例追踪一遍，只看关键几步（数值均由程序实测）：

区间	$dp_{l,r,0}$	$dp_{l,r,1}$	说明
$[1,1]$	1	0	初值，只记一个方向
$[2,2]$	1	0	初值
$[3,3]$	1	0	初值
$[4,4]$	1	0	初值
$[1,2]$	1	1	$h_1<h_2$ ：可由 $[2,2]$ 向左扩； $h_2>h_1$ ：可由 $[1,1]$ 向右扩
$[2,3]$	1	1	同理
$[3,4]$	1	1	同理
$[1,3]$	2	2	$dp_{1,3,0}=dp_{2,3,0}+dp_{2,3,1}=2$ ， $dp_{1,3,1}=dp_{1,2,0}+dp_{1,2,1}=2$
$[2,4]$	2	2	同理
$[1,4]$	4	4	$dp_{1,4,0}=dp_{2,4,0}+dp_{2,4,1}=4$ ， $dp_{1,4,1}=dp_{1,3,0}+dp_{1,3,1}=4$

读表要点：每一行只依赖上一行的结果，这正是按长度递推的含义；单点行只有一列非零，是防重复计数的关键；最后一行两列相加 $4+4=8$ ，与样例输出一致。

代码

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/**
 * 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-23 23:13
 * update_at: 2026-10-23 23:13
 */
#include <bits/stdc++.h>
using namespace std;

const int MOD = 19650827;

static int h[1005]; // h[i]：理想队形中第 i 个人的身高（下标从 1 开始）
static int dp[1005][1005][2]; // dp[l][r][0/1]：已构成目标区间 [l,r]，最后插入者在左端(0)/右端(1) 的方案数

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

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

    for (int i = 1; i <= n; ++i) {
        dp[i][i][0] = 1;
    }

    // dp[l][r][0/1]：已经构成目标区间 [l, r]，
    // 且最后插入的人在左端/右端时的方案数。
    for (int len = 1; len < n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;

            if (dp[l][r][0]) {
                if (l > 1 && h[l - 1] < h[l]) {
                    dp[l - 1][r][0] = (dp[l - 1][r][0] + dp[l][r][0]) % MOD;
                }
                if (r < n && h[r + 1] > h[l]) {
                    dp[l][r + 1][1] = (dp[l][r + 1][1] + dp[l][r][0]) % MOD;
                }
            }

            if (dp[l][r][1]) {
                if (l > 1 && h[l - 1] < h[r]) {
                    dp[l - 1][r][0] = (dp[l - 1][r][0] + dp[l][r][1]) % MOD;
                }
                if (r < n && h[r + 1] > h[r]) {
                    dp[l][r + 1][1] = (dp[l][r + 1][1] + dp[l][r][1]) % MOD;
                }
            }
        }
    }

    cout << (dp[1][n][0] + dp[1][n][1]) % MOD << '\n';
    return 0;
}

复杂度

状态数是所有区间 $(l, r)$ 乘 2 种“最后插入端点”，共 $O(n^2)$ 个；每个状态只做常数次加法与取模。

时间复杂度 $O(n^2)$ ；
空间复杂度 $O(n^2)$ ，数组 dp[1005][1005][2] 在 $n=1000$ 时约 $8\ \text{MB}$ 。

写法变体：f/g 双数组

同一算法还有一种更紧凑的“拉”式实现：把 $dp_{l,r,0/1}$ 换成两个二维数组—— $f_{l,r}$ 记最后插入的是左端， $g_{l,r}$ 记最后插入的是右端。长区间直接从短区间拉取，两个来源合并成一行，用 $(h_x < h_y)$ 的真值当 $0/1$ 系数：

f_{l,r} = (\,h_l < h_{l+1}\,)\, f_{l+1,r} + (\,h_l < h_r\,)\, g_{l+1,r},\qquad g_{l,r} = (\,h_l < h_r\,)\, f_{l,r-1} + (\,h_{r-1} < h_r\,)\, g_{l,r-1}.

单点初值仍只记一边： $f_{i,i} = 1$ 、 $g_{i,i} = 0$ 。长度 $2$ 的区间从单点拉取时，两个来源指向的是同一个人，只计一次，正好躲开“单点双计”的坑——这和正文“单点只置 $dp_{i,i,0} = 1$ ”是同一件事的另一种写法。

写法灵感来自洛谷题解《合唱队》（zhylj，uid 34238）的 f/g 双数组风格，下面的代码为独立重写，与 main.cpp 全量对拍 301 组（300 组随机数据 + $n=1$ 边界）输出完全一致。两种写法复杂度同为 $O(n^2)$ ，选择纯看口味：main.cpp 的推式与正文推导方向一致，这里给出的拉式转移行数更少。

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/**
 * 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-24 10:19
 * update_at: 2026-10-24 10:19
 */
// main-zhylj.cpp：P3205 合唱队 的写法变体（f/g 双数组拉式）。
// 与 main.cpp 同一算法（区间 DP + 计数），区别只在写法：
//   1. 不用 dp[l][r][2] 三维表，改用 f/g 两个二维数组；
//   2. 转移写成「拉式」：长区间 [l,r] 从短区间 [l+1,r]、[l,r-1] 拉取；
//   3. 两个来源合并成一行，用 (h[x] < h[y]) 的真值当 0/1 系数。
// 写法灵感来自洛谷题解 zhylj (uid 34238) 的 f/g 双数组风格，代码为独立重写。
#include <bits/stdc++.h>
using namespace std;

const int MOD = 19650827;

static int h[1005]; // h[i]：理想队形中第 i 个人的身高（下标从 1 开始）
static int f[1005][1005]; // f[l][r]：已构成 [l,r]、最后插入的是左端 h[l] 的方案数
static int g[1005][1005]; // g[l][r]：已构成 [l,r]、最后插入的是右端 h[r] 的方案数

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

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

    // 单点区间只记一边：单点的「最后插入者」左右端是同一个人，
    // 两边都置 1 会把方案数翻倍（n=1 的答案会变成 2）。
    for (int i = 1; i <= n; ++i) {
        f[i][i] = 1;
    }

    // 拉式转移：[l,r] 的最后插入者是 h[l] 时，上一步的区间是 [l+1,r]，
    // 要比的人是它的最后插入者（落在 h[l+1] 或 h[r] 上）；右端对称。
    // (h[x] < h[y]) 成立取 1、否则取 0，直接当系数，两个来源合并成一行。
    for (int len = 2; len <= n; ++len) {
        for (int l = 1; l + len - 1 <= n; ++l) {
            int r = l + len - 1;
            f[l][r] = (f[l + 1][r] * (h[l] < h[l + 1]) + g[l + 1][r] * (h[l] < h[r])) % MOD;
            g[l][r] = (f[l][r - 1] * (h[l] < h[r]) + g[l][r - 1] * (h[r - 1] < h[r])) % MOD;
        }
    }

    cout << (f[1][n] + g[1][n]) % MOD << '\n';
    return 0;
}

总结

这道题的难点不在转移，而在把“依次插入”反过来读成“连续区间向外扩张”。一旦确认了“已入队的人占据理想队形的一段连续区间”“要比较的人就是最后插入的端点”，状态 $(l, r, \text{左/右})$ 就自然浮现，转移也就只是检查两个大小关系。

实现上有三个容易翻车的点：

单点只令 $dp_{i,i,0}=1$ ，两个方向都置 $1$ 会让 $n=1$ 的答案变成 2；
必须先枚举长度再枚举左端点，保证长区间用到的短区间已经算好；
累加时立即取模，否则中间结果会超出 int。

最后附两组手算结论，可以用来检查自己的实现：

严格递增的 $h$ 答案为 $2^{n-1}$ （样例 $n=4$ 得 $8$ ）。
严格递减的 $h$ 在 $n \geqslant 2$ 时答案为 $0$ 。理由：设第一个站出来的是 $h_i$ 。此后队形右端永远是 $h_i$ ，因为 $i$ 右侧的元素全都比 $h_i$ 小，按规则只能插到左端；要得到严格递减的 $h$ ，右端必须恰好是 $h_n$ ，于是 $i = n$ 。但 $h_n$ 是最小值，第二轮无论遇到谁都只能插到左端，那样 $h_n$ 会离开右端——矛盾。

图示解析

这张图把本题的建模、转移、实现检查和常见坑点压缩到一页，适合读完正文后复盘。

目录

形式化题目

暴力解法

思路

代码

复杂度

瓶颈

正解

关键观察

思路

代码

复杂度

写法变体：f/g 双数组

总结

图示解析