这道题的数据n只有不到50，所以我一开始思考的是搜索，可惜记忆化学的不是很好，暴搜直接tle了，但是仍然能够拿到60分。

所以下面还是把我的搜索代码放出来：

读写换了更快的格式化输入输出，也不能过所有点，有大佬会用记忆化的可以指教一下。

#include<iostream>
#include<cstdio>
using namespace std;
int count = 0, Max = -1;
void backtracking(int startindex, int* c, int n, int beginlevel, int maxlevel) {
    if (beginlevel > maxlevel || beginlevel < 0 || startindex >= n) {
        if (startindex >= n && beginlevel <= maxlevel && beginlevel >= 0) {
            ++count;
            if (Max < beginlevel)Max = beginlevel;
        }
        return;
    }
    beginlevel += c[startindex];
    backtracking(startindex + 1, c, n, beginlevel, maxlevel);
    beginlevel -= 2 * c[startindex];
    backtracking(startindex + 1, c, n, beginlevel, maxlevel);
    beginlevel += c[startindex];
}
int main() {
    int n, beginlevel, maxlevel;
    scanf("%d %d %d", &n, &beginlevel, &maxlevel);
    int c[55] = { 0 };
    for (int i = 0; i < n; i++)scanf("%d", &c[i]);
    backtracking(0, c, n, beginlevel, maxlevel);
    if (count == 0)cout << -1;
    else cout << Max;
    return 0;
}

搜索过不了的题就只能想其他算法了。。。首先想到的就是DP了，因为这道题和以前刷过的一道目标和的问题很像，都是分别对一组数分两组，一组相加一组相减得到最后结果。

那道题的背包大小需要解一个多项式方程得到，这道题很直接，说明了背包大小是0-maxlevel，所以我们按照DP模板来直接分析：

1.确定DP数组含义：

DP数组开成DP[55][1005],典型的一维表示物品，记录状态；另一维表示背包，记录背包大小。

对于确定的i和j，DP[i][j]表示的是“状态”，即在当前状态下（选择是否装入物品i的纠结状态下，即纠结到底应该升调还是降调），是否可以通过上一音调状态升调或降调得到,如果可以得到，记录为1，不可以则记录为0.

如此，我们每个状态都是独立的，仅仅与上一状态关联，当我们把每一次变调都取舍了之后，最后一个状态就是所有我们最后可以到达的声调。

2.确定状态转移方程和遍历顺序：

按照1中理论，写出如下方程：

for(int i=1;i<=n;i++){
    for(int j=0;j<=maxlevel;j++){
        if(j-c[i]>=0&&dp[i-1][j-c[i]])dp[i][j]=1;
        if(j+c[i]<=maxlevel&&dp[i-1][j+c[i]])dp[i][j]=1;
    }
}

3.对最后的结果集分析：

最后一个结果，即DP[n]代表的就是所以可以达到的升调，我们取它最大值，只需要倒序遍历取第一个状态1即可。

下面给出我的AC代码：

#include<iostream>
using namespace std;
int main(){
    int n,beginlevel,maxlevel,max=-1;
    cin>>n>>beginlevel>>maxlevel;
    int c[55]={0},dp[55][1005]={0};
    dp[0][beginlevel]=1;
    for(int i=1;i<=n;i++)cin>>c[i];
    for(int i=1;i<=n;i++){
        for(int j=0;j<=maxlevel;j++){
            if(j-c[i]>=0&&dp[i-1][j-c[i]])dp[i][j]=1;
            if(j+c[i]<=maxlevel&&dp[i-1][j+c[i]])dp[i][j]=1;
        }
    }
    for(int i=maxlevel;i>=0;i--){
        if(dp[n][i]){
            cout<<i;
            return 0;
        }
    }
    cout<<-1;
    return 0;
}

最后偷了个懒，用了两个return 0，这种写法是不推荐的，但是我太懒了，将就着看吧。

这道题应该也可以用滚动数组来对背包进行一维空间优化，但是正如我所说的，我太懒了，所以懒得想，大家将就着想一下吧。

好了，就这样吧。