tag：背包问题
【题目大意】
开始有一个数begin，给一个长为n的序列，ci，每次操作可以选择把开始的数加或减ci，变为新的数，之后再上一次的数的基础上加或减。要求每次操作之后的数要大于等于0，小于等于max，求最后一次操作之后这个数的最大值。如果没有满足要求的解输出-1.
【冷静分析】
dp数组f[i][j]表示第i次操作后能否到达j位置（bool）
易知：
f[0][begin]=1
若j+c[i]<=max或j-a[i]>=0，且上一个位置为true
则f[i][j+a[i]],f[i][j-a[i]]为true
i从1到n，j从0到max循环即可
结果输出：
因为要最大值，所以j从max-->0，如果f[n][j]为true，输出，return 0
如果一直没有，就输出-1
标程如下
#include<bits/stdc++.h>
using namespace std;
int c[51],n,beginn,maxn;
bool f[51][1005];
int main()
{
scanf("%d%d%d",&n,&beginn,&maxn);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
f[0][beginn]=1;
for(int i=1;i<=n;i++){
for(int j=0;j<=maxn;j++){
if(f[i-1][j] && j+c[i]<=maxn) f[i][j+c[i]]=1;
if(f[i-1][j] && j-c[i]>=0) f[i][j-c[i]]=1;
}
}
for(int j=maxn;j>=0;j--){
if(f[n][j]){
cout<<j<<endl;
return 0;
}
}
cout<<-1<<endl;
return 0;
}