自动搬运

查看原文

来自洛谷，原作者为

	zy AFO

搬运于2025-08-24 21:39:46，当前版本为作者最后更新于2021-01-02 21:03:09，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

啊哈，题目在这里

题意很明显嘛

三个背包

不知道大佬们说的函数背包是什么东东，~~虽然的却很形象~ ~

甲：

当时只是觉得甲可以根据他给的式子直接来写对应体积的价值然后来跑$01$背包

乙：

对于每个个数处理一手，然后依旧跑$01$背包

丙：

完全背包

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#define N 1000010
using namespace std;
int re() {
	int p=0; char i=getchar();
	while(i<'0'||i>'9')	i=getchar();
	while(i>='0'&&i<='9')	p=p*10+i-'0',i=getchar();
	return p;
}
int n,m,cnt;
int w[N],v[N],r[N];
int f[N];
int main()
{
	n=re(); m=re();
	if(n==0||m==0) {
		cout<<0<<endl;
		return 0;
	}
	for(int i=1;i<=n;i++)
	{
		int op,x,y,z;
		op=re();x=re();y=re();
		if(op==1)
		{
			for(int j=1;j<=m;j++)
			{
				if(x*j-y<=0) continue;
				v[++cnt]=j;
				w[cnt]=j*(j*x-y);
				r[cnt]=1;
			}
		}
		if(op==2)
		{
			int k=1;	z=re();
			while(z>0)
			{
				int mi=min(k,z);
				w[++cnt]=mi*x;
				v[cnt]=mi*y;
				r[cnt]=1;
				z-=k;	k<<=1;
			}
		}
		if(op==3)
		{
			w[++cnt]=x;
			v[cnt]=y;
			r[cnt]=0;
		}
	}
	for(int i=1;i<=cnt;i++)
	{
		if(r[i]==0)
		{
			for(int j=v[i];j<=m;j++)	f[j]=max(f[j-v[i]]+w[i],f[j]);
		}
		else {
			for(int j=m;j>=v[i];j--)	f[j]=max(f[j-v[i]]+w[i],f[j]);
		}
	}
	cout<<f[m]<<endl;	
return 0;
}

如有不妥之处或不明白之处，欢迎指出来qwq