[HAOI2012] 音量调节

题意

有 n 次调音量操作。

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

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

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

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

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

思路

先看最直接的暴力：

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 次时
某个音量 v 是否能够达到

于是设：

dp[i][v] 表示调完前 i 次之后，音量 v 是否可达

这张表说明状态定义：

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

如果 dp[i - 1][v] = true，那么第 i 次可以尝试两种转移：

如果 v + c[i] <= maxLevel，就让 dp[i][v + c[i]] = true
如果 v - c[i] >= 0，就让 dp[i][v - c[i]] = true

初始化时只有起点可达：

dp[0][beginLevel] = true

全部转移完以后，从 maxLevel 倒着找第一个 dp[n][v] = true 的音量，就是最后能达到的最大音量。如果整行都没有可达状态，答案就是 -1。

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
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#include <bits/stdc++.h>
using namespace std;

const int MAXN = 55;
const int MAXV = 1005;

int n, begin_level, max_level;
int change_value[MAXN];
bool dp[MAXN][MAXV]; // dp[i][v] 表示调完前 i 次后，音量 v 是否可达

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

void solve() {
    dp[0][begin_level] = true;

    for (int i = 1; i <= n; i++) {
        for (int v = 0; v <= max_level; v++) {
            if (!dp[i - 1][v]) {
                continue;
            }

            int up = v + change_value[i];
            int down = v - change_value[i];

            if (up <= max_level) {
                dp[i][up] = true;
            }
            if (down >= 0) {
                dp[i][down] = true;
            }
        }
    }

    for (int v = max_level; v >= 0; v--) {
        if (dp[n][v]) {
            cout << v << '\n';
            return;
        }
    }

    cout << -1 << '\n';
}

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

    read_input();
    solve();

    return 0;
}

复杂度

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

总结

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

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

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

一图流解析

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