题目内容

P1833

大意:上学路上,看樱花,给出起始时间和终止时间,每棵樱花树都要 t_i 时间看,有 c_i 美学值,最多看 a_i 次(a_i=0 则无限次),求最高美学值。

解题思路

混合背包,将 0-1 背包,完全背包和多重背包混合在了一起,具体的思路还是二进制拆分,只需要将每一个物品拆分成 2^j 的形式即可,然后全部当作 0-1 背包处理即可,当然也可以单独拆分处理,这里没写。

方程还是熟悉的 f[j]=max(f[j],f[j-t[i]]+c[i]);

#include <cstdio>
#define max(a,b) (a>b?a:b)

int T,n,totn,f[1010],t[100010],c[100010];

int main()
{
    int teh,tem,tsh,tsm;
    scanf("%d:%d %d:%d %d",&tsh,&tsm,&teh,&tem,&n);//注意读入数据的处理,使用 scanf 会很方便
    T=(teh-tsh)*60+tem-tsm;//计算时间
    int tt,cc,a;
    for(int i=1;i<=n;i++)
    {
        scanf("%d %d %d",&tt,&cc,&a);
        if(!a)
            a=999999;//如果是完全背包的话,可以先将次数令为无限大
        int cnt=0;
        for(int j=1;j<=a && cnt<=T;j<<=1)//常规二进制拆分
        {
            cnt+=j;
            a-=j;
            t[++totn]=tt*j,c[totn]=cc*j;
        }
        if(a && cnt<=T)
            t[++totn]=tt*a,c[totn]=cc*a;
    }
    for(int i=1;i<=totn;i++)
        for(int j=T;j>=t[i];j--)
            f[j]=max(f[j],f[j-t[i]]+c[i]);
    printf("%d\n",f[T]);
    return 0;
}
最后修改日期:2020年2月27日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。