[HAOI 2012] 音量调节

知识点

动态规划、可达性、状态转移

解题思路

用布尔数组表示处理前i首歌后各音量是否可达。初始只有beginLevel可达。读入每次变化c后，枚举旧音量v，只把合法的v+c、v-c写入全新的数组。全部处理后从maxLevel向下寻找首个可达值。

正确性说明

初始状态正确。任意合法的第i首歌音量必由上一首歌的某个可达音量加c或减c得到；转移又只生成这些合法音量，因此归纳维护了全部且仅有的可达集合。最后取最大者即可。

易错点

每首歌必须改变一次，不能保留原音量；必须用新数组，防止本轮重复使用同一个变化；中途无可达音量后不能重新开始。

复杂度

时间O(n·maxLevel)，空间O(maxLevel)。

参考代码（GNU C++17）

#include<bits/stdc++.h>
using namespace std;
int main(){int n,b,m;cin>>n>>b>>m;vector<char>dp(m+1);dp[b]=1;for(int i=0,c;i<n;++i){cin>>c;vector<char>ndp(m+1);for(int v=0;v<=m;++v)if(dp[v]){if(v+c<=m)ndp[v+c]=1;if(v-c>=0)ndp[v-c]=1;}dp.swap(ndp);}for(int v=m;v>=0;--v)if(dp[v]){cout<<v<<'\n';return 0;}cout<<-1<<'\n';}