自动搬运

查看原文

来自洛谷，原作者为

	cy20110922 **

搬运于2025-08-24 23:07:15，当前版本为作者最后更新于2024-12-23 13:57:49，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析

先看一眼算法标签，哦是背包啊。再看一眼题目，既然可以多次游玩，那一定就是完全背包！

思路

本题跟完全背包不同的一点是他要先学习完游戏才能开始玩，所以只要把 $dp$ 数组下标从 $j$ 改为 $t-j$ 就可以了。对于完全背包的做法 $dp[j]$ 表示时间为 $j$ 时所获得的最大分数。然后我们可以在创建一个数组 $maxn$ 来实时保存最大值。最后便利一遍 $maxn$ 找出最大值就可以了。

上代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int dp[60000],c[60000],w[60000],t[60000],maxn[6000],sum=0;
signed main(){
	int n,m;
	cin >> n >> m;
	for(int i=1;i<=n;i++){
		cin >> t[i] >> w[i] >> c[i];
		for(int j=m;j>=t[i];j--){
			dp[j]=maxn[j-t[i]];
		}
		for(int j=w[i]+t[i];j<=m;j++){
			dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
			maxn[j]=max(maxn[j],dp[j]);
		}
	}
	for(int i=1;i<=m;i++){
		sum=max(sum,maxn[i]);
	}
	cout << sum;
	return 0;
}