题解 | #[HAOI2012]音量调节#

原题传送门

闲来无事，又刷一题。

题目理解

这是一个比较特殊的动态规划问题。吉他手需要在每首歌之前调整音量，可以选择调高或调低给定的音量值，但音量必须在 0 到 maxLevel 之间。我们需要找出最后一首歌能达到的最大音量。

我们可以从中提取出以下几个关键点：

初始音量为 beginLevel
每次调整可以选择在上一首歌的基础上加或减 c[i]
音量范围限制在 [0, maxLevel]
需要找到最后一首歌的最大可能音量
如果因为一些原因（如：在此前的任意一首歌中，不可避免的出现音量 $s \ge maxLevel$ 或者 $s \le 0$ ）导致无法得到最后一首歌的最大可能音量，则输出-1。

解题思路

这里需要使用一种特殊的动态规划方法：

状态定义： [i][j] 为布尔值（不再是一个数值），表示经过前 i 次调整后，音量 j 是否可以达到。
初始状态： dp[0][beginLevel] = true ，表示在演奏歌曲之前，即初始时只有起始音量可以达到。
状态转移：对于第i次调整（使用 c[i] ）：
- 如果当前音量j可以达到，那么：
  - 如果 j + c[i] <= maxLevel ，则 j + c[i] 也可以达到
  - 如果 j - c[i] >= 0 ，则 j - c[i] 也可以达到
结果查找：在完成所有调整后，从 maxLevel 倒序查找第一个可以达到的音量，即为答案。

AC 代码

#include<bits/stdc++.h>
using namespace std;

const int N = 1010;
int n, b, m;
bool dp[N][N]; // dp[i][j]表示前i次调整后音量j是否可达
int c[N];

int main() {
    cin >> n >> b >> m;
    
    // 初始化：第0次调整后，只有初始音量可达
    dp[0][b] = true;
    
    for(int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    
    // 动态规划过程
    for(int i = 1; i <= n; i++) {
        for(int j = 0; j <= m; j++) {
            if(dp[i-1][j]) { // 如果前i-1次调整后音量j可达
                // 尝试调高音量
                if(j + c[i] <= m) {
                    dp[i][j + c[i]] = true;
                }
                // 尝试调低音量
                if(j - c[i] >= 0) {
                    dp[i][j - c[i]] = true;
                }
            }
        }
    }
    
    // 从最大音量开始向下查找第一个可达的音量
    for(int i = m; i >= 0; i--) {
        if(dp[n][i]) {
            cout << i << endl;
            return 0;
        }
    }
    
    // 如果没有可达的音量，输出-1
    cout << -1 << endl;
    return 0;
}

复杂度分析

可以直观地看出：

时间复杂度为 $O(n \times maxLevel)$ 其中 $n$ 是调整次数， $maxLevel$ 是最大音量
空间复杂度： $O(n \times maxLevel)$ ，当然，示例代码使用的是二维数组，可以使用滚动数组优化到 $O(maxLevel)$