感觉这道题评 $困难$ 太过了，因为这明显是一道小学生DP

题目描述

一个吉他手准备参加一场演出。

他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都要改变一次音量。

在演出开始之前，他已经做好了一个列表，里面写着在每首歌开始之前他想要改变的音量是多少。

每一次改变音量，他可以选择调高也可以调低。

音量用一个整数描述。

输入文件中给定整数 $beginLevel$ ，代表吉他刚开始的音量，以及整数 $maxLevel$ ，代表吉他的最大音量。

音量不能小于 $0$ 也不能大于 $maxLevel$。

输入文件中还给定了 $n$ 个整数 $c_1,c_2,c_3,…,c_n$，表示在第 $i$ 首歌开始之前吉他手想要改变的音量是多少。

吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。

算法1

($DP$) $O(n \times maxlevel)$

定义

$dp[i][j]$ 表示第 $i$ 个的音量能否达到 $j$ 。

$val[i]$ 表示在第 $i$ 首歌开始之前吉他手想要改变的音量。

初始化 $dp[0][beginlevel]=true$ ，即第 $0$ 个的音量可以达到 $beginlevel$

随后开始枚举 $i$ 和 $j$ 。

状态转移方程：

$If$ $dp[i-1][j]=true$ $:$ $dp[i][j-val[i]]=true \And dp[i][j+val[i]]=true$

意思是如果前一首歌的音量达到了 $j$ ,又因为从上次到这次可以变化 $val[i]$ ，那么当前状态可以由 $dp[i-1][j]$ 延伸出来。

最后再从后往前遍历一遍，如果 $dp[n][i]=true(1\leq n\leq maxlevel)$ ，则马上输出这个 $i$ 。

C++ 代码

#include <cstdio>

using namespace std;

const int ma=5005;

int a[ma];

bool dp[ma][ma];//dp[i][j]:第i个能否到达音量j 

int main(void)
{
    int n,beginlevel,maxlevel;

    scanf("%d%d%d",&n,&beginlevel,&maxlevel);

    for(register int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }

    dp[0][beginlevel]=true;

    for(register int i=1;i<=n;i++)
    {
        for(register int j=0;j<=maxlevel;j++)
        {
            if(dp[i-1][j]==true)
            {
                dp[i][j-a[i]]=true;

                dp[i][j+a[i]]=true;
            }
        }
    }

    for(register int i=maxlevel;i>=1;i--)
    {
        if(dp[n][i]==true)
        {
            printf("%d\n",i);

            return 0;
        }
    }

    printf("-1\n");

    return 0;
}