EEchoyukii @ 2019-11-07 20:48:13
样例没过,求dalao修改,谢谢
#include<iostream>
#include<cstdio>
using namespace std;
inline int read(){
register int x=0,v=1,ch=getchar();
while(!isdigit(ch)){if(ch=='-')v=-1;ch=getchar();}
while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
return x*v;
}
const int MAX=65,N=32005;
int W,n,u[MAX],f[N];
int w[MAX],v[MAX],ch[MAX][10],cnt[MAX],c1,c2;
int main(){
W=read(),n=read();
for(register int i=1;i<=n;++i){
w[i]=read();v[i]=w[i]*read();
u[i]=read();
if(u[i]!=0)ch[u[i]][++cnt[u[i]]]=i;
}
for(register int i=1;i<=n;++i){
if(u[i]==0){//是主件
c1=ch[i][1];c2=ch[i][2];
for(register int j=W;j>=w[i];--j)f[j]=max(f[j],f[j-w[i]]+v[i]);
//只选主件
for(register int j=W;j>=w[i]+w[c1];--j)f[j]=max(f[j],f[j-w[i]-w[c1]]+v[i]+v[c1]);
//主件+附件1
if(cnt[i]==2){
for(register int j=W;j>=w[i]+w[c2];--j)f[j]=max(f[j],f[j-w[i]-w[c2]]+v[i]+v[c2]);
//主件+附件2
for(register int j=W;j>=w[i]+w[c1]+w[c2];--j)f[j]=max(f[j],f[j-w[i]-w[c1-w[c2]]]+v[i]+v[c1]+v[c2]);
//主件+附件1+附件2
}
}
}
printf("%d\n",f[W]);
return 0;
}
by 蒟蒻本人 @ 2019-11-07 20:55:03
if(cnt[i]>=1)
for(register int j=W;j>=w[i]+w[c1];--j)f[j]=max(f[j],f[j-w[i]-w[c1]]+v[i]+v[c1]);
//主件+附件1
by 蒟蒻本人 @ 2019-11-07 20:55:07
@AK永动机
by EEchoyukii @ 2019-11-07 20:57:40
@蒟蒻本人 谢谢dalao