Description
共\(n\)次操作，每次操作有一个值\(a_i\),同时给定一个初始值\(start\),对于每次操作，可以将值\(k\)加或减\(a_i\)(\(k\)初始=\(start\)),求经过这\(n\)操作后\(k\)的最大值。
Solution
其实这是一个01背包的变形。
这和01背包有何关系呢？
回顾一下经典01背包：有若干件物品，每个物品有重量和价值两个参数，有一个背包，背包容量有限，求背包在不超过容量的前提下价值最大。
那本题呢？
有若干次操作，每次操作可以选择加或减，求最大值？
我们可以反向思考，用\(f\)数组存储该音量是否可以达到，最后统计答案从MAX_LEVEL倒着搜是不是就可以解决了？！
设计状态：\(f_{i,j}\)表示前\(i\)次操作音量\(j\)是否可达。
考虑转移：音量\(j\)可以通过\(j+a_i\)或者\(j-a_i\)得到（\(a_i\)为每次操作的参数）。由于我们一次转移是依据上一次操作的，故枚举时应当先枚举操作次数，再转移。
这样我们就能确保每次转移都能依据上一次操作，同时满足无后效性。
还是非常可爱的题呢QAQ！
Code
/* 01背包变形
朴素01背包需求一件物品选or不选的max，而本题求经过n次操作后的max
我们可以求每个音量是否可以得到！
还是两个状态，f[i][j]表示经过i次操作后的音量j是否可得。
容易发现可以递推得到
最后倒着从max_level搜如果可以实现直接输出即可。
*/
#include <iostream>
#include <cstdio>
#include <algorithm>
#define N 1010
using namespace std;
int n,begin_level,max_level;
int f[N][N];
int c[N];
int main()
{
scanf("%d%d%d",&n,&begin_level,&max_level);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
f[0][begin_level] = 1;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=max_level;j++)
{
int x = j+c[i],y = j-c[i];
if(y>=0&&f[i-1][y]) f[i][j] = 1;
if(x <= max_level && f[i-1][x]) f[i][j] = 1;
}
}
for(int i=max_level;i>=0;i--)
{
if(f[n][i])
{
cout<<i<<endl;
return 0;
}
}
cout<<"-1"<<endl;
return 0;
}