自动搬运

查看原文

来自洛谷，原作者为

	lqhsr ☝这个家伙很♂，✓什么也没有留↓

搬运于2025-08-24 21:56:27，当前版本为作者最后更新于2019-09-17 22:35:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

保证你能懂&&无脑坑点揭示

这题一看显然是个多重背包二进制拆分转成01背包

然而这样只有50pts

暴力就不解释啦，具体看100pts的解释吧

#include<bits/stdc++.h>
using namespace std;
int n,m,c,ji,f[100005];
struct node{
	int s,id;
}w[100000],v[100000];
inline int read(){
	register int x=0;
	register char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
int main(){
	cin>>n;
	for(register int i=1;i<=n;++i){
		register int cw=read(),cv=read(),c=read();
		register int now=1;
		while(now<=c){
			w[++ji].s=cw*now,v[ji].s=cv*now;
			w[ji].id=i,v[ji].id=i;
			c-=now,now*=2;
		}
		if(c){
			w[++ji].s=cw*c,v[ji].s=cv*c;
			w[ji].id=i,v[ji].id=i;
		}
	}
	cin>>m;n=ji;
	for(register int l=1;l<=m;++l){
		register int cn=read()+1,V=read();
		for(register int i=1;i<=n;++i){
			if(w[i].id!=cn){
				for(register int j=V;j>=w[i].s;--j){
					f[j]=max(f[j],f[j-w[i].s]+v[i].s);
				}
			}
		}
		printf("%d\n",f[V]);
		memset(f,0,sizeof(f));
	}
}

100pts:

考虑怎么优化

我们知道背包其实就是把每一种放法都考虑一遍，我们设的状态是f[i][j]表示考虑到第i个总体积为j的最大价值

而我们要求的是不考虑第i种物品时的最大价值

诶 这不就是f[i-1][V]么～～～

不对其实这样后面的物品就没有被考虑到

那怎么办呢

于是我们可以从后往前再DP一次表示从后面往前面考虑的最大价值

把两个背包的结果合并就是所求啦

然而还有一个恶心的地方

由于搬运题目的人的疏忽

1 ≤ q ≤ 3*105

其实是

1 ≤ q ≤ 3*1e5

我在这上面WA了整整10次。。。(所以我才来写题解纪念纪念)

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,c,ji;
ll f1[100005][1005],f2[100005][1005];
struct node{
    int id;ll s;
}w[300005],v[300005];
inline int read(){
	register int x=0;
	register char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
	return x;
}
int main(){
	cin>>n;
	for(register int i=1;i<=n;++i){
		register int cw=read(),cv=read(),c=read();
		register int now=1;
		while(now<=c){//二进制拆分，不懂的可以记住
			w[++ji].s=cw*now,v[ji].s=cv*now;
            w[ji].id=i,v[ji].id=i;
			c-=now,now*=2;
		}
		if(c){
			w[++ji].s=cw*c,v[ji].s=cv*c;
            w[ji].id=i,v[ji].id=i;
		}//拆分结束
	}
	cin>>m;
	n=ji;//更新物品数量
	for(int i=1;i<=n;i++){//正向01背包
		for(int j=0;j<=1000;j++)f1[i][j]=f1[i-1][j];
		for(int j=1000;j>=w[i].s;j--){
			f1[i][j]=max(f1[i][j],f1[i-1][j-w[i].s]+v[i].s);
		}
		
	}
	for(int i=n;i>=1;i--){//反向01背包
		for(int j=0;j<=1000;j++)f2[i][j]=f2[i+1][j];
		for(int j=1000;j>=w[i].s;j--){
			f2[i][j]=max(f2[i][j],f2[i+1][j-w[i].s]+v[i].s);
		}
		
	}
	for(int k=1;k<=m;k++){
		int cn=read()+1,V=read();
		ll ans=0;
        int l=0,r=0;//因为同一种物品可能已被拆成多件物品而这种物品都不能被考虑于是我们要找到不包括这种物品的f1和f2
        while(w[l+1].id<cn&&l<n)++l;
        r=l;
        while(w[r+1].id<=cn&&r<n)++r;
		for(int j=0;j<=V;j++){//这是枚举分配给该种物品之前的物品多少空间
			ans=max(ans,f1[l][j]+f2[r+1][V-j]);//不懂的可以拿样例模拟一下，温馨提示：样例可被拆分成9件物品
		}
		printf("%lld\n",ans);
	}
}