背包

多重背包
多重背包模板

#include<stdio.h>
#define max(a,b) ((a)>(b)?(a):(b))
const int N = 10010;
int t[N],c[N],p[N];//时间，美学，观赏次数 
int f[1010];
int main(){
    int h1,h2,m1,m2,n,time;
    scanf("%d:%d %d:%d %d",&h1,&m1,&h2,&m2,&n);
    time = (h2-h1)*60+m2-m1;
    for(int i = 1;i<=n;i++){
        scanf("%d%d%d",&t[i],&c[i],&p[i]);
    } 
    for(int i = 1;i<=n;i++){
        int k = p[i];
        if(p[i]==0){
            for(int j = time-t[i];j>=0;j--)
                f[j]=max(f[j],f[j+t[i]]+c[i]); 
        }
        else{
            for(int z = 1;z<=p[i];z<<=1){
                p[i]-=z;
                for(int j = 0;j<=time-z*t[i];j++){
                    f[j] = max(f[j],f[j+z*t[i]]+z*c[i]);
                    //printf("%d %d %d %d %d\n",i,z,j,f[j],k);
                }   
            }
            if(p[i])
            for(int j = 0;j<=time-p[i]*t[i];j++){
                f[j] = max(f[j],f[j+p[i]*t[i]]+p[i]*c[i]);
                //printf("%d %d %d %d\n",i,j,f[j],k);
            }
        }
    }
    int ans = 0;
    for(int i = 0;i<=time;i++)ans = max(ans,f[i]);
    printf("%d",ans);
}