P1877 [HAOI2012] 音量调节
[题目链接：P1877 HAOI2012] 音量调节 - 洛谷
题目描述
一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前都需要改变一次音量。在演出开始之前，他已经做好一个列表，里面写着每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。
音量用一个整数描述。输入文件中整数 $beginLevel$，代表吉他刚开始的音量，整数 $maxLevel$，代表吉他的最大音量。音量不能小于 $0$ 也不能大于 $maxLevel$。输入中还给定了 $n$ 个整数 $c_1, c_2, c_3, \cdots, c_n$，表示在第 $i$ 首歌开始之前吉他手想要改变的音量是多少。
吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。
60 分解法
DFS 深度优先搜索
考虑第 $dep + 1$ 个物品选或不选的情况：
dfs(dep + 1, val + c[i])dfs(dep + 1, val - c[i])
#include <bits/stdc++.h>
using namespace std;const int N = 55, MAXN = 1005;
int n, m, c[N], BL, dp[MAXN], ans = -1;void dfs(int dep, int val) {if (val < 0 || val > m)return;if (dep == n) {ans = max(ans, val);return;}dfs(dep + 1, val + c[dep + 1]);dfs(dep + 1, val - c[dep + 1]);
}int main() {cin >> n >> BL >> m;for (int i = 1; i <= n; i++)cin >> c[i];dfs(0, BL);cout << ans;return 0;
}
100 分解法
到达型 01 背包问题
$dp_{i,j}$ 表示选取前 $i$ 个物品，音量 $j$ 能否达到。
状态转移方程：
$dp_{i,j} = dp_{i-1,j-c_i} \ || \ dp_{i-1,j+c_i}$
#include <bits/stdc++.h>
using namespace std;const int N = 55, MAXN = 1005;
int n, m, c[N], BL;
bool dp[N][MAXN];int main() {cin >> n >> BL >> m;for (int i = 1; i <= n; i++)cin >> c[i];dp[0][BL] = 1;for (int i = 1; i <= n; i++) {for (int j = 0; j <= m; j++) {if (j - c[i] >= 0 && dp[i - 1][j - c[i]] == 1)dp[i][j] = 1;else if (j + c[i] <= m && dp[i - 1][j + c[i]] == 1)dp[i][j] = 1;}}for (int i = m; i >= 0; i--)if (dp[n][i]) {cout << i;return 0;}cout << -1;return 0;
}