Solution

转移方程比较简单，这里就直接给出了。代表第首歌结束的时候是的音量，并且可以满足前面首歌都不低于0和不大于的条件。

初始条件就是。

转移方程就是下面给出的，注意不要越界了。

状态总数，转移时间复杂度，空间复杂度。

解决之后考虑如何做下优化吧，第一步首先知道对于第个物品可以更新的状态只有，使用滚动数组压缩空间，可以压缩到空间复杂度是。

第二个优化就是卡常大师，把枚举状态的过程进行加速，最终优化出来的代码就是下面的样子了，这样可以把数据出的更大很多。

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

typedef long long ll;
const int N = 50 + 7;
const int M = 1e3 + 7;

int n, m, maxi;
bitset<M> f[2], p;
int a[N];
int op = 0;

int main() {
    cin >> n >> m >> maxi;
    for (int i = 0; i <= maxi; ++i)
        p[i] = 1; // 保证大于maxi的都变成0
    for (int i = 1; i <= n; ++i)
        cin >> a[i];
    f[0][m] = 1;
    for (int i = 1; i <= n; ++i) {
        op ^= 1;
        f[op].reset();
        f[op] |= (f[op ^ 1] >> a[i]);
        f[op] |= (f[op ^ 1] << a[i]) & p;
    }
    for (int i = maxi; ~i; --i)
        if (f[op][i]) {
            cout << i << endl;
            return;
        }
    cout << -1 << endl;
    return 0;
}