自动搬运

查看原文

来自洛谷，原作者为

	ben090302 不辨真假，勿问虚实|AFO on 2024.11.30

搬运于2025-08-24 23:06:12，当前版本为作者最后更新于2024-11-22 19:24:33，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

题意简单，就是一个多重背包。

但是这题的数据范围实在是反常。

我们发现这题的容量出奇的小，可以接受 $S^2$ 左右的算法，带个 $\log$ 也不算困难。

多重背包的标准复杂度最优是 $nS$ 也就是单调队列优化，如果信仰足够强大也许能过，但是这个时间限制我觉得有点紧张，我们不妨考虑更优秀的做法。

首先看向这个 $k_i$，我们会发现这个 $k$ 的数据范围只是吓人用的，就算每个物品重量都只有 $1$，我们也拿不到 $10^9$ 个数，这是不可能的，最多只能拿 $\lfloor\frac{S}{w} \rfloor$ 个，后面除法默认取整省去不写。

还没完，如果我们只看同种重量的物品，我们也只需要观察价值前 $\frac{S}{w}$ 个，再往后显然是没有意义的。可以注意到重量的数量和 $S$ 是一致的，分析时我们就认为重量正好是 $S$ 种来分析复杂度。

简单分析一下现在物品数量的上界，是 $\sum_{w=1}^n \frac{S}{w}$，这是一个调和级数，大概约等于 $S\log S$。

我们直接对这些剩下的物品做简单的 $01$ 背包，复杂度 $O(S^2\log S+n\log n)$，后面那个 $n\log n$ 来自于排序。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
const int SN=2005;
int n,S;

struct node{
	int v,w,k;
	bool operator<(node x){
		return v<x.v;
	}
}a[N];
struct nd{
	int v,w;
}it[SN*30];
vector<node> item[SN];
int cnt;
int f[SN];
signed main(){
	cin>>S>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i].v>>a[i].w>>a[i].k;
		item[a[i].w].push_back(a[i]);
	}
	for(int i=1;i<=S;i++) sort(item[i].begin(),item[i].end());
	for(int i=1;i<=S;i++){
		int j=0;
		while(j<=S/i and !item[i].empty()){
			it[++cnt]={item[i].back().v,item[i].back().w};
			j++;
			item[i].back().k--;
			if(!item[i].back().k) item[i].pop_back();
		}
	}
	for(int i=1;i<=cnt;i++){
		for(int j=S;j>=it[i].w;j--){
			f[j]=max(f[j],f[j-it[i].w]+it[i].v);
		}
	}
	cout<<f[S];
}