[HAOI2012] 音量调节

题意

有 n 次调音量操作。

初始音量是 beginLevel
每次操作要么把当前音量加上 c[i]
要么把当前音量减去 c[i]
任意时刻音量都必须保持在 [0, maxLevel] 之间

要求最后一首歌开始时的音量尽量大。如果无论怎样调都会在某一步越界，就输出 -1。

这张表展示样例里的可达音量是怎样一步一步变化的：

处理到第几首歌前	可达音量集合
初始	`{5}`
第 1 次改 `5`	`{0, 10}`
第 2 次改 `3`	`{3, 7}`
第 3 次改 `7`	`{10}`

从表里可以看到，每一步只关心"当前哪些音量还能达到"，不需要记录具体是怎么走到这里的。最后一行里最大的可达音量是 10，所以样例答案就是 10。

思路

一句话本质：每步只有"加 c_i"和"减 c_i"两个固定方向，且音量范围受限——用可行性 DP 逐层记录前 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#include <bits/stdc++.h>
using namespace std;

// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。

const int MAXN = 55;

int n, begin_level, max_level;
int change_value[MAXN];
int answer = -1;

// 枚举每一次调音量时选择加还是减。
// 复杂度是 O(2^n)，只适合小数据验证。
void dfs(int idx, int volume) {
    if (idx > n) {
        answer = max(answer, volume);
        return;
    }

    int up = volume + change_value[idx];
    int down = volume - change_value[idx];

    if (up <= max_level) {
        dfs(idx + 1, up);
    }
    if (down >= 0) {
        dfs(idx + 1, down);
    }
}

void read_input() {
    cin >> n >> begin_level >> max_level;
    for (int i = 1; i <= n; i++) {
        cin >> change_value[i];
    }
}

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

    read_input();
    dfs(1, begin_level);
    cout << answer << '\n';

    return 0;
}

brute.cpp 枚举每一次调音量时选择"加"还是"减"，只保留不越界的分支。

这个做法显然正确，但复杂度是 $O(2^n)$ ， $n = 50$ 时已经不可能直接枚举。

每步只有两个固定方向，状态之间是什么关系？

第 i 步的 c_i 是固定值。如果上一步音量是 v，下一步只能是 v + c_i（如果 ≤ maxLevel）或 v - c_i（如果 ≥ 0）。每个状态的后继数量最多两个而且完全确定。

要不要记录具体怎么走？

不需要。题目只关心最终能达到的最大音量，中间路径不重要。只要知道"前 i 步后音量 v 能否达到"就足够决定下一步。

怎么用 DP 表示这条可达链？

设 dp[i][v] 表示前 i 次调节后，音量 v 是否可达。

初始：dp[0][beginLevel] = true
第 i 步：对所有上一步可达的 v，如果 v + c_i ≤ maxLevel 则 dp[i][v + c_i] = true；如果 v - c_i ≥ 0 则 dp[i][v - c_i] = true

最后从 maxLevel 向 0 扫描，找到第一个 dp[n][v] = true 的 v 就是答案。整行都不可达则输出 -1。

状态表

这张表说明状态定义：

状态	含义
`dp[i][v]`	调完前 `i` 次后，音量 `v` 是否可达

DP 公式

设 $dp_{i,v}$ 表示调完前 $i$ 次之后，音量 $v$ 是否可达。初始化：

dp_{0,begin}=true

若 $dp_{i-1,v}=true$ ，则第 $i$ 次可以向上或向下调：

dp_{i,v+c_i}=true\quad (v+c_i\leqslant maxLevel)

dp_{i,v-c_i}=true\quad (v-c_i\geqslant 0)

最终从大到小找满足 $dp_{n,v}=true$ 的最大 $v$ ，不存在则输出 $-1$ 。

公式解释：音量 DP 是可达性状态。每次调节只能在上一次可达音量的基础上加或减 c_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/**
 * 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-08-08 23:13
 * update_at: 2026-08-08 23:13
 * dp[i][j] 表示前i首可达音量j
 */
#include <bits/stdc++.h>
using namespace std;

const int maxl = 1005;
int n, bg, mx;
bool dp[55][maxl];

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n >> bg >> mx;
    dp[0][bg] = true;
    for (int i = 1; i <= n; ++i) {
        int c; cin >> c;
        for (int j = 0; j <= mx; ++j) {
            if (!dp[i - 1][j]) continue;
            if (j + c <= mx) dp[i][j + c] = true;
            if (j - c >= 0) dp[i][j - c] = true;
        }
    }
    for (int j = mx; j >= 0; --j)
        if (dp[n][j]) { cout << j << "\n"; return 0; }
    cout << "-1\n";
    return 0;
}

复杂度

时间复杂度： $O(n * maxLevel)$
空间复杂度： $O(n * maxLevel)$

总结

这题的关键不是枚举所有加减方案，而是把它改写成"状态是否可达"的动态规划。

以后看到下面这种结构时，可以优先往可达性 DP 上想：

每一步只有少量固定转移
状态范围不大
问题本质是"某个状态能不能到"“最终最优的可达状态是什么”

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。