Luogu

分析

这是一道DP题。
设$f[i][j]$表示第$i$首歌音量为$j$的状态能否达到。
那么每首歌就是一个阶段。对于每一个$j$，我们都要进行状态转移。
状态转移方程也不难得出：

$f[i][j]=f[i-1][j-c[i-1]]||f[i-1][j+c[i]]$

边界：

$f[0][beginLevel]=true,f[0][i]=false(i\neq beginLevel)$

那么答案就是所有$f[n][i]=true$的情况中的最大的$i$。
怎样才是无解？即不存在这样的$i$。

还有转移时的下标越界问题，需注意。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
using namespace std;
bool f[60][1010]; //f[i][j]表示第i首歌音量为j的状态 
int c[60];
int beginLevel,maxLevel,n;
int main()
{
    scanf("%d%d%d",&n,&beginLevel,&maxLevel);
    for (int i=1;i<=n;i++) scanf("%d",&c[i]); //输入
    f[0][beginLevel]=true; //边界
    for (int i=1;i<=n;i++) //DP
        for (int j=0;j<=maxLevel;j++)
        {
            if (j-c[i]>=0&&f[i-1][j-c[i]]) f[i][j]=true; //注意越界
            if (j+c[i]<=maxLevel&&f[i-1][j+c[i]]) f[i][j]=true;
        }
    for (int i=maxLevel;i>=0;i--) //倒退找最大i
    {
        if (f[n][i])
        {
            printf("%d\n",i);
            return 0;
        }
    }
    printf("-1\n"); //无解
    return 0;
}