EEchoyukii @ 2019-11-07 21:37:56
只AC前两个点,求助dalao,谢谢
3的数据
input:
2000 10
500 1 0
400 4 0
300 5 1
400 5 1
200 5 0
500 4 5
400 4 0
320 2 0
410 3 0
400 3 5
output:
7430
#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]);
//只选主件
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
}
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;
}