自动搬运

查看原文

来自洛谷，原作者为

	Diamiko 此人已退役，不用留言了，看不见

搬运于2025-08-24 21:41:17，当前版本为作者最后更新于2020-04-15 09:53:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

分析题目

要素无非就以下几个：

• 总时间，总体力

• 每棵树的桃数

• 每棵树所耗的时间和体力

• 每棵树能摘的次数

再转变一下

• 总体积

• 每个物品的价值

• 每个物品的消耗

• 每个物品使用的次数

不难看出，这就是多重背包

注意点：

背包总体积的处理

乍一看，题目有两个“体积”，一个时间，一个体力。但实际并非如此。

因为我们每走一步，时间和体力都减一，只要时间到 0 或者 体力到 1 就不能再走了，所以背包体积就可以取 总时间 和 总体力-1 的较小值 。

另外，为什么总体力要减一？

由于PFT不是机器人，所以他的体力并不是无限的，他不想摘很多的桃以至体力为0，而白白把桃给Life。

体力不能到0的哦~

物品消耗的处理

每个物品的消耗就是(0,0)到当前坐标的距离，但需要注意的是这里的距离不是欧几里得距离！！

因为PFT只能上下左右移动，不能斜着跑。

所以每个物品的消耗：

设当前坐标为(x,y)，则消耗为2*(x+y)

为什么乘2？因为是往返啊……

代码

这里使用了二进制优化

#include<iostream>
#include<cstdio>
using namespace std;
struct Object
{
	long long cost,value,number;
	//每个物品的消耗，价值和次数
	//每个桃数的距离，桃子数量，和采摘次数
}a[10005];
long long dp[10005];
int n,h,l,Time,Tili,Bag;
//总物品数，行，列，总时间，总体力，背包体积
void ZeroOnePack(int cost,int value)
{
	for(int i=Bag;i>=cost;i--)
	{
		dp[i]=max(dp[i],dp[i-cost]+value);
	}
}
//01背包板子
void CompletePack(int cost,int value)
{
	for(int i=cost;i<=Bag;i++)
	{
		dp[i]=max(dp[i],dp[i-cost]+value);
	}
}
//完全背包板子
void MultiPack(int cost,int value,int amount)
{
	if(Bag<=cost*amount)
	{
		//背包体积小于等于物品的总体积
		//那么随便拿，完全背包
		//Trace On!
		CompletePack(cost,value);
		return;
	}
	for(int k=1;k<amount;k<<=1)
	{
		ZeroOnePack(cost*k,value*k);
		amount-=k;
	}
	ZeroOnePack(cost*amount,value*amount);
	//二进制优化的过程↑
}
//上面是二进制优化的多重背包板子
//如果有不会二进制优化的同学，可以把我这个板子粘下来背
//我感觉这个板子相比别的大佬写的板子还是很简单好记的
int main()
{
	scanf("%d%d%d%d",&h,&l,&Time,&Tili);
	n=h*l;
	//获得总物品数
	int cnt=0;
	//记录物品下标
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=l;j++)
		{
			scanf("%lld",&a[++cnt].value);
			//输入当前桃子数量，即物品价值
			a[cnt].cost=i+j<<1;
			//同时处理出当前桃数的距离
			//位运算，等价于(i+j)*2
		}
	}
	cnt=0;
	//重新输入，清零下标
	for(int i=1;i<=h;i++)
	{
		for(int j=1;j<=l;j++)
		{
			scanf("%lld",&a[++cnt].number);
			//输入可采摘次数
		}
	}
	Bag=min(Time,Tili-1);
	//计算背包体积
	for(int i=1;i<=n;i++)
	{
		MultiPack(a[i].cost,a[i].value,a[i].number);
	}
	printf("%lld\n",dp[Bag]);
	return 0;
}

附赠多重背包二进制优化的板子

void ZeroOnePack(int cost,int value)
{
	for(int i=Bag;i>=cost;i--)
	{
		dp[i]=max(dp[i],dp[i-cost]+value);
	}
}
void CompletePack(int cost,int value)
{
	for(int i=cost;i<=Bag;i++)
	{
		dp[i]=max(dp[i],dp[i-cost]+value);
	}
}
void MultiPack(int cost,int value,int amount)
{
	if(Bag<=cost*amount)
	{
		CompletePack(cost,value);
		return;
	}
	for(int k=1;k<amount;k<<=1)
	{
		ZeroOnePack(cost*k,value*k);
		amount-=k;
	}
	ZeroOnePack(cost*amount,value*amount);
}
signed main()
{
	......
	//省略输入……
	for(int i=1;i<=n;i++)
	{
		MultiPack(a[i].cost,a[i].value,a[i].number);
	}
	printf("%lld\n",dp[Bag]);
}

都看完了，不点个赞再走吗（滑稽