bzoj-2748___音量调节 —— dp+01背包

本文主要是介绍bzoj-2748___音量调节 —— dp+01背包，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：传送门

题目大意：

    $n$个数，起始音量为$beginLevel$，最大音量为$maxlevel$，下面$n$个数$c$_$1$、$c$_$2$$......$$c$_$n$，每次可以选择增大$c$_$i$的音量或者减少相应音量，问最后一次后最大音量为多少，若只能小于$0$或者大于$maxlevel$则输出$-1$。。。。。

解题思路：

    都说是脑残题，确实是脑残题，用背包暴力一下就行了。每个数遍历一遍背包大小，增加或者减小若在范围内就加到dp里，最后输出最后一个数的最大背包大小即可。

代码思路：

    遍历每个数，顺序判断背包大小加上或者减去音量时的情况。起始$dp[0][st]=1$

核心：脑残、脑残、脑残，但对于新手来说十个不错的理解题，脑残

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;int n, m, st;
int w[55];
int dp[55][1005];int main() {scanf("%d%d%d", &n, &st, &m);for(int i=1; i<=n; i++)scanf("%d", &w[i]);memset(dp, 0, sizeof(dp));dp[0][st]=1;for(int i=1; i<=n; i++)for(int j=0; j<=m; j++) {	//注意是逆序、逆序、逆序！！if(j-w[i]>=0) dp[i][j] = max(dp[i][j], dp[i-1][j-w[i]]);if(j+w[i]<=m) dp[i][j] = max(dp[i][j], dp[i-1][j+w[i]]);}for(int i=m; i>=0; i--)if(dp[n][i]) {printf("%d\n", i);return 0;}printf("-1\n");
}

这篇关于bzoj-2748___音量调节 —— dp+01背包的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---