解题报告 P1833 樱花

题目内容

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