$Result$

---

$Hyperlink$

https://www.luogu.com.cn/problem/P1833

---

$Description$

有一个$m$体积的背包，有$n$种物品，有的有无限个，有的有有限个，选择每个物品都有一定的体积及其贡献
求最大贡献

数据范围：
$n\le 10^4,m\le 10^3$

---

$Solution$

显然是一个混合背包，设$f_j$表示空间为$j$的最大贡献
完全背包的情况直接递推即可
至于有限个的情况，考虑将背包进行二进制拆分，然后跑0/1背包即可（当然你也可以写单调队列优化一下）

前者时间复杂度：$O(nmlogm)$
后者时间复杂度：$O(nm)$

---

$Code1$

#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;int n,a1,a2,b1,b2,m,nn,ti,ci,pi;
int T[200001],C[200001],P[200001],f[1010];
inline LL read()
{char c;LL d=1,f=0;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
inline void fj(int ti,int ci,int pi)
{int x=1;while((x<<1)-1<=pi) T[++nn]=x*ti,C[nn]=x*ci,P[nn]=x,x<<=1;while((x<<1)-1>pi) x>>=1;x=(x<<1)-1;if(pi-x!=0) T[++nn]=(pi-x)*ti,C[nn]=(pi-x)*ci,P[nn]=pi-x;return;
}
signed main()
{a1=read();b1=read();a2=read();b2=read();n=read();m=(a2-a1)*60+b2-b1;for(register int i=1;i<=n;i++){ti=read();ci=read();pi=read();if(pi==0) T[++nn]=ti,P[nn]=pi,C[nn]=ci;else fj(ti,ci,pi);}for(register int i=1;i<=nn;i++){if(P[i]==0)for(register int j=T[i];j<=m;j++) f[j]=max(f[j],f[j-T[i]]+C[i]);elsefor(register int j=m;j>=T[i];j--)f[j]=max(f[j],f[j-T[i]]+C[i]);}printf("%d",f[m]);
}

$Code2$

#include<queue>
#include<cctype>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;int n,a1,a2,b1,b2,m,nn,ti,ci,pi,l,r;
int f[1010];
deque< pair<int,int> >q;
inline LL read()
{char c;LL d=1,f=0;while(c=getchar(),!isdigit(c)) if(c=='-') d=-1;f=(f<<3)+(f<<1)+c-48;while(c=getchar(),isdigit(c)) f=(f<<3)+(f<<1)+c-48;return d*f;
}
signed main()
{a1=read();b1=read();a2=read();b2=read();n=read();m=(a2-a1)*60+b2-b1;for(register int i=1;i<=n;i++){ti=read();ci=read();pi=read();if(pi==0) for(register int j=ti;j<=m;j++) f[j]=max(f[j],f[j-ti]+ci);elsefor(register int j=0;j<ti;j++){while(q.size()) q.pop_front();l=1;r=0;int maxp=(m-j)/ti;for(register int p=0;p<=maxp;p++){while(q.size()&&f[j+ti*p]-ci*p>=q.back().second) q.pop_back();q.push_back(make_pair(p,f[j+ti*p]-ci*p));while(q.size()&&q.front().first<p-pi) q.pop_front();f[j+ti*p]=max(f[j+ti*p],q.front().second+ci*p);}}}printf("%d",f[m]);
}