动态规划-音量调节

对于%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