题目：P1877 [HAOI2012] 音量调节
题目描述
一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都需要改变一次音量。在演出开始之前，他已经做好一个列表，里面写着每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。
音量用一个整数描述。输入文件中整数b e g i n L e v e l beginLevelbeginLevel，代表吉他刚开始的音量，整数m a x L e v e l maxLevelmaxLevel，代表吉他的最大音量。音量不能小于0 00也不能大于m a x L e v e l maxLevelmaxLevel。输入中还给定了n nn个整数c 1 , c 2 , c 3 , ⋯ , c n c_1,c_2,c_3,\cdots,c_nc1,c2,c3,⋯,cn，表示在第i ii首歌开始之前吉他手想要改变的音量是多少。
吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。
输入格式
第一行依次为三个整数n nn，b e g i n L e v e l beginLevelbeginLevel和m a x L e v e l maxLevelmaxLevel。
第二行依次为n nn个整数c 1 , c 2 , c 3 , ⋯ , c n c_1,c_2,c_3,\cdots,c_nc1,c2,c3,⋯,cn。
输出格式
输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于0 00或者高于m a x L e v e l maxLevelmaxLevel，输出-1。
输入输出样例 #1
输入 #1
3 5 10 5 3 7输出 #1
10说明/提示
1 ≤ n ≤ 50 1\le n\le 501≤n≤50，1 ≤ c i ≤ m a x L e v e l 1\le c_i\le maxLevel1≤ci≤maxLevel，1 ≤ m a x L e v e l ≤ 1000 1\le maxLevel\le 10001≤maxLevel≤1000，0 ≤ b e g i n L e v e l ≤ m a x L e v e l 0\le beginLevel\le maxLevel0≤beginLevel≤maxLevel。
代码1（二维数组）
#include<bits/stdc++.h>usingnamespacestd;constintN=50+10,M=1000+10;intn,beg,V,v,f[N][M],ans=-1;intmain(){scanf("%d%d%d",&n,&beg,&V);f[0][beg]=1;for(inti=1;i<=n;i++){cin>>v;for(intj=V;j>=0;j--){if(f[i-1][j]&&j+v<=V)f[i][j+v]=1;if(f[i-1][j]&&j-v>=0)f[i][j-v]=1;}}for(intj=V;j>=0;j--)if(f[n][j]){ans=j;break;}printf("%d",ans);return0;}代码2（二维数组）
#include<bits/stdc++.h>usingnamespacestd;constintN=50+10,M=1000+10;intn,beg,V,v,f[N][M],ans=-1;intmain(){scanf("%d%d%d",&n,&beg,&V);f[0][beg]=1;for(inti=1;i<=n;i++){cin>>v;for(intj=V;j>=0;j--){if(j+v<=V)f[i][j]=f[i][j]||f[i-1][j+v];if(j-v>=0)f[i][j]=f[i][j]||f[i-1][j-v];}}for(intj=V;j>=0;j--)if(f[n][j]){ans=j;break;}printf("%d",ans);return0;}
