[Luogu]P1877

题目链接

本题属于01背包模型。(到达型01背包+条件限制)
在写题过程中一直困扰我的一个问题：
为啥这个状态转移能保证过程中的量没由超出题目规定呢？

	//dp[i][j]  考虑前i次调节音乐大小，能否使音量大小为jfor(int i=1;i<=n;i++){cin>>v;for(int j=0;j<=Max;j++){if(j+v<=Max&&dp[i-1][j])dp[i][j+v]=1;if(j-v>=0&&dp[i-1][j])dp[i][j-v]=1;//假设两个if都不满足，是不是可以直接输出-1呢？}}

我们知道，第$[i]$层是由第$[i-1]$层转移过来的，当第$i-1$层的数据不能满足题目要求时，第$[i-1]$层的数据都为$0$，导致之后的第n层的数据都为$0$；也就是无法到达第$n$层，故当我们要得出第$n$次调整音量大小后的最大音量时，从$j=Max$到$j=1$扫描 dp$[n][j]$,第一个为$1$的$j$值就是结果,若全为$0$输出$-1$

问题解决
代码如下：

/*** @filename: P1877* @author: Noel* @date: 2020-03-15 * @time: 16:13:38*/
#include
using namespace std;
typedef long long LL;
#define RG register int
#define ULL unsigned long long
const int INF=2147483647; 
const int MAX=10e7;
bool dp[55][1010];
int main(){int v;int n,st,Max;cin>>n>>st>>Max;dp[0][st]=1;for(int i=1;i<=n;i++){cin>>v;for(int j=0;j<=Max;j++){if(j+v<=Max&&dp[i-1][j])dp[i][j+v]=1;if(j-v>=0&&dp[i-1][j])dp[i][j-v]=1;}}for(int i=Max;i>=0;i--){if(dp[n][i]){cout<<i;return 0;}}cout<<"-1";return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！