题解 P1833 【樱花】

· · 题解

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

一.朴素的做法

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背包,完全背包和多重背包不会的可以看这里

这里主要讲优化

代码

        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;
}