解题报告：luogu P1833

题目链接：P1833 樱花
从大佬那里盗题真爽
混合背包，转化成多重背包即可，一本通讲的太迷，没有看懂，就写了个自己认为好理解的。
当然\(O(nW\max t)\)是会\(T\)掉的，可以用二进制进行优化，时间复杂度是\(O(nW\log\max t)\)的，可以通过本题。
不要拆我台说可以用单调队列优化至\(O(nW)\)，我只能说：博主太菜了，不会。

\(Code\):

#include<iostream>
#include<cstdio>
using namespace std;
const int MAXN=10005;
inline int read()
{
    int x=0;
    char c=getchar();
    while(c<'0'||c>'9')
    {
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+(c^'0');
        c=getchar();
    }
    return x;
}
int _,__,___,____,n,w;
int t[MAXN],c[MAXN],p[MAXN],now; 
int dp[1005];
int main()
{
    scanf("%d:%d%d:%d",&_,&__,&___,&____);
    w=(___-_)*60+(____-__);
    n=read();
    for(int i=1;i<=n;i++){t[i]=read(),c[i]=read(),p[i]=read();if(p[i]==0) p[i]=w/t[i]+5;}
    //容易发现，对于完全背包的部分，赋这个值就足够了，思考下为啥
    for(int i=1;i<=n;i++)
    {
        for(int k=1;p[i]>0;k<<=1)
        {
            now=min(k,p[i]);
            for(int j=w;j>=now*t[i];j--) dp[j]=max(dp[j],dp[j-now*t[i]]+now*c[i]);
            p[i]-=now;
        }
    }
    printf("%d\n",dp[w]);
    return 0;
} 

莫吐槽毒瘤变量名与换行码风。

解题报告：luogu P1833

原文：https://www.cnblogs.com/tlx-blog/p/12513322.html