@[Knox_Zuopu](/user/1089634) 再开大100倍就过了
by Orz___zrO @ 2024-02-22 07:04:15
```CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[100100];
ll t[100100],c[100100],f[100100],num;
int main()
{
int h1,m1,h2,m2,n,T;
scanf("%d:%d %d:%d",&h1,&m1,&h2,&m2);
cin>>n;
T=h2*60+m2-h1*60-m1;
for(int i=1;i<=n;i++)
{
int tx,cx,px;
cin>>tx>>cx>>px;
if(px==0)
{
t[++num]=tx;
c[num]=cx;
f[num]=2;
}
else
{
int k=1;
while(px>=k)
{
t[++num]=k*tx;
c[num]=k*cx;
f[num]=1;
px-=k;
k<<=1;
}
if(px)
{
t[++num]=px*tx;
c[num]=px*cx;
f[num]=1;
}
}
}
for(int i=1;i<=num;i++)
{
if(f[i]==1)
{
for(int j=T;j>=t[i];j--)
{
dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
}
}
else if(f[i]==2)
{
for(int j=t[i];j<=T;j++)
{
dp[j]=max(dp[j],dp[j-t[i]]+c[i]);
}
}
}
cout<<dp[T];
return 0;
}
```
也许10倍也行,我没测
by Orz___zrO @ 2024-02-22 07:05:05
@[Orz___zrO](/user/1055592) 感谢,现在意识到二进制优化的时候背包数会增加
by Knox_Zuopu @ 2024-02-22 13:01:38