多重背包优化-打包
陈子骏
2018-04-01 16:51:19
```cpp
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int n,c[10001],t[10001],p[10001];
int dp[1001],t2;
void ze(int we,int va){
for(int i=t2;i>=we;i--) dp[i]=max(dp[i],dp[i-we]+va);
}
int main()
{
int t1[5];
scanf("%d:%d%d:%d",&t1[1],&t1[2],&t1[3],&t1[4]);
t2=60*(t1[3]-t1[1])+t1[4]-t1[2];
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d%d%d",&t[i],&c[i],&p[i]);
for(int i=1;i<=n;i++)
{
if(p[i]==0)
{
for(int j=t[i];j<=t2;j++)
if(dp[j]<dp[j-t[i]]+c[i])
dp[j]=dp[j-t[i]]+c[i];
}
else{
int k=1;
while(k<p[i]){
ze(k*t[i],k*c[i]);
p[i]-=k;
k*=2;
}
ze(p[i]*t[i],p[i]*c[i]);
}
}
printf("%d",dp[t2]);
return 0;
}
```