AcWing 7. 混合背包问题
标签：mes end wing code mem const out 混合背包 01背包
#include
#include
#includeusing namespace std ;
const int N=1010;
int f[N],g[N],q[N];
int n,m;
int a[N];
int main() {
cin>>n>>m;
for(int i=1; i) {
int v,w,s;
cin>>v>>w>>s;
if(s==0) { //完全背包
for(int j=v; j)
f[j]=max(f[j],f[j-v]+w);
} else {
if(s==-1)//如果是01背包
s=1;//换成s就只有1
memcpy(g,f,sizeof f);
for(int j=0; j) {
int hh=0,tt=-1;
for(int k=j; kv) {
if(hhv)
hh++;
if(hhtt)
f[k]=max(f[k],g[q[hh]]+(k-q[hh])/v*w);
while(hhw)
tt--;
q[++tt]=k;
}
}
}
}
coutendl;
return 0;
}
AcWing 7. 混合背包问题
标签：mes end wing code mem const out 混合背包 01背包
原文地址：https://www.cnblogs.com/QingyuYYYYY/p/12003907.html
评论