自动搬运

查看原文

来自洛谷，原作者为

	Y_B_Y 这个家伙很懒....

搬运于2025-08-24 21:30:51，当前版本为作者最后更新于2019-08-28 20:11:54，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

混和背包问题的一种简单但比二进制优化慢一点的做法

一.朴素的做法

1.时间输入:

cin>>小时1>>符号':'(char型)>>分钟1>>小时2>>符号':'>>分钟2;//当cin输入到数据类型不一样的是后它会跳到下一个数据类型一样的

如 12:55 13:21输入完就是

第一个. 12 第二. : 第三. 55 第四. 13 第五. : 第六. 21 //被分开了

总时间:60*(小时2-小时1)+分钟2-分钟1 (单位是分钟)

上面的总时间就是60*(13-12)+21-55=26分钟

2.背包:

01背包,完全背包和多重背包不会的可以看这里

这里主要讲优化

• $dp[j]$表示消耗了$j$分钟最多可以有多少美学值,$a[i]$表示第i朵花最多可以看多少次

• 当$a[i]=0$时,用完全背包

• 其他时候用多重背包(01可以算是只能一次的多重背包)

代码

        for(int i=1;i<=n;i++)
	{
		if(a[i]==0)//如果为完全背包
		{
			for(int j=t[i];j<=tz;j++) dp[j]=max(dp[j],dp[j-t[i]]+c[i]);//记得是正序
		}
		else
		{
		        for(int l=1;l<=a[i];l++)//重复a[i]次01背包的结果就相当于最多取a[i]个的多重背包
		        for(int j=tz;j>=t[i];j--) //01背包,倒序
			{
				dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
			}
		}
	}

二.优化

我们可以发现当第$i$个朵花,重复第$k$次01背包时,对于第$i$朵花$dp[k*t[i]]$前(不包括本身)的值都是已经确定了的,由于前面都是确定的就不要再循环到了

解释

我们先看第一次01背包时,$dp[t[i]]$之前的都是可以确定对于第$i$朵花,是一定为0的(也就他们的贡献为0),因为消耗那么多时间根本不够看第$i$朵花

所以在第一次01背包中:$dp[2*t[i]-1]$由已经确定的$dp[t[i]-1]$得来,$dp[2*t[i]-2]$由已经确定的$dp[t[i]-2]$得来...$dp[t[i]]$由已经确定的$dp[0]$得来,所以他们在之后的第二次01背包中也是确定的

第二次01背包与第一次一样由$dp[2*t[i]]$之前都是确定的可以得出$dp[3*t[i]]$之前都是确定的给第三次01用,这样重复直到次数的上限结束

代码

	for(int i=1;i<=n;i++)
	{
		if(a[i]==0)//完全背包和前面一样
		{
			for(int j=t[i];j<=tz;j++) dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
		}
		else
		{
		    for(int l=1;l<=a[i];l++)
		    for(int j=tz;j>=l*t[i];j--) //倒序,前面确定的不要循环到
			{
				dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
			}
		}
	}

完整代码

#include<bits/stdc++.h>
using namespace std;
int c[100001],a[1000001],t[1000001],te1,te2,ts1,ts2,n,tz;//c[],t[]为题目等于,a[]表示最多看的次数,te1小时1,te2分钟1,ts1小时2,ts2分钟2,tz总时间
int dp[1001];//dp[j]表示消耗了j分钟最多可以有多少美学值
char cc;//符号':'
int main()
{
	cin>>te1>>cc>>te2>>ts1>>cc>>ts2;
	tz=60*(ts1-te1)+ts2-te2;
	cin>>n;
	for(int p=1;p<=n;p++) scanf("%d%d%d",&t[p],&c[p],&a[p]);
	for(int i=1;i<=n;i++)
	{
		if(a[i]==0)
		{
			for(int j=t[i];j<=tz;j++) dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
		}
		else
		{
		    for(int l=1;l<=a[i];l++)
		    for(int j=tz;j>=l*t[i];j--) 
			{
				dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
			}
		}
	}
	cout<<dp[tz];
	return 0;
}