洛谷 P1877 [HAOI2012] 音量调节 题解

题目链接

洛谷 P1877 [HAOI2012] 音量调节

注意题目中为改变而不是变为。

思路分析

一个 0-1 背包的判段可行性，注意上下边界判断，防止数组下标溢出。

代码呈现

#include<bits/stdc++.h>
using namespace std;const int N=55,M=1010;
int n,beginLevel,maxLevel;
int c[N];
bool dp[N][M];int main(){scanf("%d%d%d",&n,&beginLevel,&maxLevel);for (int i=1;i<=n;++i) scanf("%d",c+i);dp[0][beginLevel]=1;for (int i=1;i<=n;++i){for (int j=maxLevel;j>=c[i];--j) dp[i][j]|=dp[i-1][j-c[i]];for (int j=maxLevel-c[i];j>=0;--j) dp[i][j]|=dp[i-1][j+c[i]];}for (int i=maxLevel;i>=0;--i){if (dp[n][i]){ printf("%d",i);return 0; } }printf("-1");return 0;
}