樱花

二进制拆分题...没什么好说的,证明看上篇博客/..

#include <bits/stdc++.h>
using namespace std;
const int N=1e4+5,M=3e5+4e4;
int t[N],c[N],p[N];
int id,n;
int T[M],val[M];
int f[1005];
inline void init()
{
    for(int i=1;i<=n;i++)
    {
        int vnt=1;
        while(true)
        {
            if(p[i]-vnt<0)
            {
                val[id]=c[i]*p[i];
                T[id]=t[i]*p[i];
                id++;
                break;
            }
            else
            {
                p[i]-=vnt;
                val[id]=c[i]*vnt;
                T[id]=t[i]*vnt;
                id++;
            }
            vnt*=2;
        }
    }
}

int main()
{
    int ca,cb,cc,cd;
    scanf("%d:%d%d:%d",&ca,&cb,&cc,&cd);
    int v=(cc-ca)*60+(cd-cb);//背包容量
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d",&t[i],&c[i],&p[i]);
        if(p[i]==0)
        {
            p[i]=1001;
        }
        p[i]=min(1001,p[i]);
    }
    init();
    for(int i=0;i<id;i++)
    {
        for(int j=v;j>=T[i];j--)
        {
            f[j]=max(f[j],f[j-T[i]]+val[i]);
        }
    }
    printf("%d\n",f[v]);
    return 0;
}