多重背包
陈子骏
2018-04-01 16:50:32
```cpp
// luogu-judger-enable-o2
#include<bits/stdc++.h>
using namespace std;
int n,c[10001],t[10001],p[10001];
int dp[1001];
int main()
{
int t1[5];
scanf("%d:%d%d:%d",&t1[1],&t1[2],&t1[3],&t1[4]);
int 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{
for(int k=1;k<=p[i];k++)
for(int j=t2;j>=t[i];j--)
if(dp[j]<dp[j-t[i]]+c[i])
dp[j]=dp[j-t[i]]+c[i];
}
}
printf("%d",dp[t2]);
return 0;
}
```