动态规划-音量调节
[HAOI2012]音量调节
https://ac.nowcoder.com/acm/problem/19990
对于%60的数据，递归是个简单又容易理解的方法。初学者可用此法：
思路：每次递归有两种情况：加或减。即： solve(curLevel + a[t], t + 1);
或 solve(curLevel - a[t], t + 1);
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 105;
int n, beginLevel, maxLevel, ans = -maxn;
int a[maxn];
// 快速读入（可以替换成scanf或printf）
void read(int &x) {
int p = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') {
p = -1;
}
c = getchar();
}
while (c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
}
//核心代码
bool solve(int curLevel, int t) {//curLevel表示当前音量，t表示第t首曲子
if (curLevel > maxLevel || curLevel < 0) {
return false;
}
//已经是最后一首曲子，更新最大值ans
if (t == n + 1) {
ans = max(ans, curLevel);
return true;
}
bool plus = solve(curLevel + a[t], t + 1);
bool minus = solve(curLevel - a[t], t + 1);
//若尝试两种情况都失败了
if (!plus && !minus) {
return false;
}
return true;
}
int main() {
read(n), read(beginLevel), read(maxLevel);
for (int i = 1; i <= n; i++) {
read(a[i]);
}
if (solve(beginLevel, 1)) {
printf("%d\n", ans);
} else {
printf("-1\n");
}
return 0;
}
/*
input:
3 5 10
5 3 7
output:
10
*/但是如何做到满分呢？这里我先说明超时原因：递归的效率比递推效率低很多
这题数据量小，可以不用大佬们所说的“滚动数组”。
1.令bool dp[i][j]为第i首曲子是否能达到音量j
2.转移方程：dp[i][j-a[i]]=1,dp[i][j+a[i]]=1.当然要有判断，是否超出音量范围。
附上满分代码如下：
#include <cstdio>
#include <iostream>
using namespace std;
const int maxn = 105;
int n, beginLevel, maxLevel, ans = -maxn;
int a[maxn];
bool f[maxn][maxn * 100];
// f[i][j]表示第i首曲子所能达到的音量
void read(int &x) {
int p = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') {
p = -1;
}
c = getchar();
}
while (c >= '0' && c <= '9') {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
}
int main() {
read(n), read(beginLevel), read(maxLevel);
for (int i = 1; i <= n; i++) {
read(a[i]);
}
f[0][beginLevel] = 1;
for (int i = 1; i <= n; i++) {
// 外层循环枚举曲子
for (int j = maxLevel; j >= 0; j--) {
// 内层循环枚举音量
if (a[i] + j <= maxLevel && f[i - 1][j]) {
f[i][j + a[i]] = 1;
}
if (j - a[i] >= 0 && f[i - 1][j]) {
f[i][j - a[i]] = 1;
}
}
}
// 第一个f[n][i]==1的值即为最大值
for (int i = maxLevel; i >= 0; i--) {
if (f[n][i]) {
printf("%d\n", i);
return 0;
}
}
printf("-1\n");
return 0;
}
/*
input:
3 5 10
5 3 7
output:
10
*/希望我（菜鸟）的解析能对大家有bang'z
