2748: [HAOI2012]音量调节
题目:传送门
题解:
sb省选题..呵呵一眼背包:
f[i][j]表示第i时刻能否为音量j
代码:
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
using namespace std;
int n,st,mx;
int a[];
bool f[][];
int main()
{
scanf("%d%d%d",&n,&st,&mx);
for(int i=;i<=n;i++)scanf("%d",&a[i]);
f[][st]=;
for(int i=;i<=n;i++)
for(int j=;j<=mx;j++)
{
if(a[i]+j<=mx && f[i-][a[i]+j])f[i][j]=;
if(j-a[i]>= && f[i-][j-a[i]])f[i][j]=;
}
bool bk=false;
for(int i=mx;i>=;i--)
if(f[n][i]){printf("%d\n",i);bk=true;break;}
if(bk==false)printf("-1\n");
return ;
}