[HAOI2012]音量调节

题意：
有一个歌手要唱n首歌，每首歌在唱之前可以调节ci的音量,上调或者下调，但不能低于0或者高于maxLevel，初始音量为beginLevel，求最后一首歌音量最大为多少，如果不能满足规则，则输出-1.

思路：
首先观察数据范围，我们发现n和maxLevel都不是很大，所有我们可以使用dp来写.

定义状态：
dp[i][j]表示第i首歌是否可以达到j的音量，值为1表示可以，为0表示不可以。

转移方程：
dp[i][j]=dp[i][j] || dp[i-1][j+ci] (上调) || dp[i-1][j-ci]（下调）;

初始化：
dp[0][beginLevel]=1;

代码：

#include<bits/stdc++.h>

#define ll long long
#define eps 1e-8

using namespace std;

const ll inf=1e9+7;

struct w
{
    int cost, wi;
} w[100005];

int a[100005], dp[105][1005];

int main()
{
    int n, b, ma;
    scanf("%d%d%d",&n,&b,&ma);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    dp[0][b]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=0;j<=ma;j++)
        {
            if(j>=a[i])
            {
                dp[i][j]|=dp[i-1][j-a[i]];
            }
            if(j+a[i]<=ma)
            {
                dp[i][j]|=dp[i-1][j+a[i]];
            }
        }
    }
    int ans=-1;
    for(int i=ma;i>=0;i--)
    {
        if(dp[n][i])
        {
            ans=i;
            break;
        }
    }
    cout << ans << endl;
    return 0;
}