[HAOI2012] 音量调节
题目描述
一个吉他手准备参加一场演出。他不喜欢在演出时始终使用同一个音量，所以他决定每一首歌之前他都需要改变一次音量。在演出开始之前，他已经做好一个列表，里面写着每首歌开始之前他想要改变的音量是多少。每一次改变音量，他可以选择调高也可以调低。
音量用一个整数描述。输入文件中整数 \(beginLevel\)，代表吉他刚开始的音量，整数 \(maxLevel\)，代表吉他的最大音量。音量不能小于 \(0\) 也不能大于 \(maxLevel\)。输入中还给定了 \(n\) 个整数 \(c_1,c_2,c_3,\cdots,c_n\)，表示在第 \(i\) 首歌开始之前吉他手想要改变的音量是多少。
吉他手想以最大的音量演奏最后一首歌，你的任务是找到这个最大音量是多少。
输入格式
第一行依次为三个整数 \(n\)，\(beginLevel\) 和 \(maxLevel\)。
第二行依次为 \(n\) 个整数 \(c_1,c_2,c_3,\cdots,c_n\)。
输出格式
输出演奏最后一首歌的最大音量。如果吉他手无法避免音量低于 \(0\) 或者高于 \(maxLevel\)，输出 -1。
样例 #1
样例输入 #1
3 5 10
5 3 7
样例输出 #1
10
提示
\(1\le n\le 50\)，\(1\le c_i\le maxLevel\)，\(1\le maxLevel\le 1000\)，\(0\le beginLevel\le maxLevel\)。
解析&Code
到达型的01背包问题
f[i][j]:前i首歌曲能否达到音量j,f[i][j]=0不能达到,f[i][j]=1表示可以达到
音量调高表示取第i件物品，音量调低表示不取第i件物品
音量为背包容量，01背包模板题（调高调低带约束）
初始条件：f[0][beginlevel]=1,没演奏前可以到达\(beginLevel\)
#include <bits/stdc++.h>
using namespace std;
int n,beginlevel,maxlevel;
int ans;
int a[51];
int f[51][1001];
int main()
{
cin >> n >> beginlevel >> maxlevel;
f[0][beginlevel]=1;
for(int i=1;i<=n;i++)
{
cin >> a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=maxlevel;j>=0;j--)
{
if(j-a[i]>=0)
{
f[i][j]=f[i][j]||f[i-1][j-a[i]];
}
if(j+a[i]<=maxlevel)
{
f[i][j]=f[i][j]||f[i-1][j+a[i]];
}
}
}
for(int i=maxlevel;i>=1;i--)
{
if(f[n][i]==1)
{
cout << i;
return 0;
}
}
cout << -1;
return 0;
}