题目链接
洛谷 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;
}