Luogu P1877 [HAOI2012]音量调节

题目

P1877 [HAOI2012]音量调节

分析

题目的意思大概就是，在一个序列中选择数，使得任何一次选择不小于0，不大于maxLevel,而且每个数要么选择正值（即调高），要么选择负值（即降低）。那么得到了一个暴力的做法，枚举每个值的符号，求最大值。复杂度O($2^n$)。顺着思路往下走，可以联想到背包问题。那么肯定是01背包啦，bool f[i][j]表示在演奏第i首歌时，音量可否达到j，如果可以则为true，否则为false。状态转移时要分情况讨论：

$$f[i][j]=f[i][j]||f[i-1][j+a[i]],j+a[i]<=maxLevel$$ $$f[i][j]=f[i][j]||f[i-1][j-a[i]],j-a[i]>=0$$
最后逆序枚举[0,maxLevel]范围内的音量，遇到第一个f[n][i]可行时，即为最大音量。
如果始终没有符合条件的f[n][i]，说明根本无法更新到第n首歌，即某一时刻出现了无论如何转移都不满足 $j+a[i]<=maxLevel$或者 $j-a[i]>=0$的情况，应输出-1。

代码

#include<cstdio>
#include<iostream>
using namespace std;
const int maxn=52;
int a[maxn];
bool f[maxn][maxn*20];
int main()
{int n,b,m,ans=0;scanf("%d%d%d",&n,&b,&m);for(int i=1;i<=n;i++)scanf("%d",&a[i]);f[0][b]=1;for(int i=1;i<=n;i++)for(int j=m;j>=0;j--){if(j+a[i]<=m)       f[i][j]=f[i][j]||f[i-1][j+a[i]];if(j-a[i]>=0)   f[i][j]=f[i][j]||f[i-1][j-a[i]];}for(int i=m;i>=0;i--)if(f[n][i]){printf("%d",i);return 0;}printf("-1");return 0;
}