自动搬运

查看原文

来自洛谷，原作者为

	jiangby **

搬运于2025-08-24 21:48:51，当前版本为作者最后更新于2018-11-02 18:17:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

看到这一道题其实很容易就看出了第一问的做法就是多重背包，然后第二问要求输出方案，那么我们很容易就会想到DP要输出方案，很简单的一个方法就是保存当前的状态从哪里转移过来的，然后倒着输出就可以了，就做一个数组d，来保存怎么转移的，很多的dp输出方案都可以用类似的方法输出，不知道的同学可以试一下。

其中d[i][j]表示状态为f[i][j]时，是由f[i-1][d[i][j]]转移过来的
void print(int x,int y){
	if(!x)return;
	print(x-1,d[x][y]);
	printf("%d ",(y-d[x][y])/w[x]);
}

普通的直接多重背包对于这一道题明显会超时，所以我们应该使用优化算法。多重背包一共两种优化（我所知道的），二进制优化和单调队列优化。一般来说用二进制优化是比单调队列快一点的，因为单调队列常数比较大，但如果用二进制优化的话个人感觉不怎么方便统计如何转移过来的，所以我在这一题选择了单调队列优化，使用单调队列优化的话统计如何转移就可以非常简单做出来了。如果你不懂如何单调队列优化我推荐一篇博客，个人感觉讲得不错。

https://blog.csdn.net/sinat_34943123/article/details/52857327

这是我昨天晚上看到这题，当场学单调队列优化真正把我看懂的一篇博客。也感谢这一位dalao的博客，没有这篇博客我肯定过不了这题

代码如下

#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<queue>
#include<vector>
#include<deque>
#include<set>
#include<map>
#define N 20005
using namespace std;
struct Node{
	int x,y;
}q1[N],q2[N];
int n,m,w[N],c[N],f[N],d[205][N];
int head1,head2,tail1,tail2;
void print(int x,int y){//打印方案 
	if(!x)return;
	print(x-1,d[x][y]);
	printf("%d ",(y-d[x][y])/w[x]);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
		scanf("%d",&w[i]);
	for(int i=1;i<=n;i++)	
		scanf("%d",&c[i]);
	scanf("%d",&m);
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++){//单调队列优化背包 
		for(int j=0;j<w[i];j++){
			head1=head2=1;
			tail1=tail2=0;
			for(int k=j,cnt=0;k<=m;cnt++,k+=w[i]){
				int xx=k/w[i];
				if(tail1-head1==c[i]){
					if(q1[head1].x==q2[head2].x)
						head2++;
					head1++;
				}
				int t=f[k]-cnt;
				q1[++tail1].x=t,q1[tail1].y=k;
				while(head2<=tail2&&t<q2[tail2].x)
					tail2--;
				q2[++tail2].x=t,q2[tail2].y=k;
				f[k]=q2[head2].x+cnt;
				d[i][k]=q2[head2].y;
			}
		}
	}
	printf("%d\n",f[m]);
	print(n,m);
	return 0;
}

PS：

1.本来我想用单调队列后，想直接看题解怎么做的单调队列，以此来学习，但题解里只有二进制优化的做法，我又没怎么看懂，就自己学，学了写这篇题解帮助一下和我一样的同学。

2.个人认为讲得比较清楚，但是平常不管是文化课还是竞赛给别人讲题基本别人听不懂。若有不懂可以私聊，我尽量回复。

3.祝NOIP2018 RP++