自动搬运

查看原文

来自洛谷，原作者为

	royzhu 这个家伙菜得很,什么都没有留下

搬运于2025-08-24 21:36:10，当前版本为作者最后更新于2018-08-17 15:03:52，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

解法一：

这题的m，n超级大， n,m<=100000

单纯的01背包肯定会TLE但是，ai和bi非常小，只ai,bi<=10 我们要如何利用ai和bi呢？

我们仔细的想一想后会发现：ai和bi一定会重复多次出现

我们可以用一个二维数组t来记录ai和bi的出现次数

然后利用二进制的思想，把t[ai][bi]个aibi分成1，2，4.....个aibi

（因为这样可以通过相加得到1到t[ai][bi]个ai，bi。但只要log（t[ai][bi]）左右的时间可做到）

例如把20分成 1 2 4 8 5

这样做了之后，我们就可以做01背包了

#include<cstdio>
#include<algorithm>//这头文件有max 函数 
using namespace std;
struct lol{int a,c;} d[100010];//d[i].a相当于ai ,d[i].c相当于bi
int f[100010],t[11][11],len=0;
int main()
{
	int n,m,k;scanf("%d %d %d",&n,&m,&k);
	for(int i=1;i<=n;i++)
	{
		int x,y;scanf("%d %d",&x,&y);
		if(t[x][y]==0){d[++len].a=x;d[len].c=y;}//可同下同时删除 
		t[x][y]++;//统计aibi的出现次数 
	}
	for(int x=0;x<=10;x++)
	{
		for(int y=0;y<=10;y++)
		{
			int v=1;
			--t[x][y];//可同上同时删除 
			while(t[x][y]>=v){d[++len].a=x*v;d[len].c=y*v;t[x][y]-=v;v*=2;} 
			//利用二进制思想分 ，len统计个数 
			if(t[x][y]>0){d[++len].a=x*t[x][y];d[len].c=y*t[x][y];t[x][y]=0;}
			//把剩下存进来 
		}
	}
	/////////////////////////01背包 
	for(int i=1;i<=len;i++)
	{
		for(int j=m;j>=d[i].a;j--)
		{
			f[j]=max(f[j],f[j-d[i].a]+d[i].c);
		}
	}
	if(f[m]>=k)printf("yes\n");
	else printf("no\n");
	printf("%d",f[m]);
}

解法二： o3+o2+01背包（黑科技）