bjrjk @ 2017-07-23 23:14:48
根本找不到哪里出错了啊……
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
using namespace std;
int n,m;
int v[65],p[65],q[65],w[65];
struct independent{
int main;
int sub1;
int sub2;
}main_good[65];
int independent_ptr;
int f[65][35000];
void insert_subgood(int main,int sub){
for(int i=1;i<=independent_ptr;i++){
if(main_good[i].main==main){
if(main_good[i].sub1==0)main_good[i].sub1=sub;
else main_good[i].sub2=sub;
break;
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>v[i]>>p[i]>>q[i];
w[i]=v[i]*p[i];
if(q[i]==0){
independent_ptr++;
main_good[independent_ptr].main=i;
}else{
insert_subgood(q[i],i);
}
}
for(int i=1;i<=independent_ptr;i++){
for(int j=0;j<=n;j++){
f[i][j]=f[i-1][j];
if(j-v[main_good[independent_ptr].main]>=0)
f[i][j]=max(f[i][j],f[i-1][j-v[main_good[independent_ptr].main]]+w[main_good[independent_ptr].main]);
if(main_good[independent_ptr].sub1!=0&&j-v[main_good[independent_ptr].main]-v[main_good[independent_ptr].sub1]>=0)
f[i][j]=max(f[i][j],f[i-1][j-v[main_good[independent_ptr].main]-v[main_good[independent_ptr].sub1]]+w[main_good[independent_ptr].main]+w[main_good[independent_ptr].sub1]);
if(main_good[independent_ptr].sub2!=0&&j-v[main_good[independent_ptr].main]-v[main_good[independent_ptr].sub2]>=0)
f[i][j]=max(f[i][j],f[i-1][j-v[main_good[independent_ptr].main]-v[main_good[independent_ptr].sub2]]+w[main_good[independent_ptr].main]+w[main_good[independent_ptr].sub2]);
if(main_good[independent_ptr].sub1!=0&&main_good[independent_ptr].sub2!=0&&j-v[main_good[independent_ptr].main]-v[main_good[independent_ptr].sub1]-v[main_good[independent_ptr].sub2]>=0)
f[i][j]=max(f[i][j],f[i-1][j-v[main_good[independent_ptr].main]-v[main_good[independent_ptr].sub1]-v[main_good[independent_ptr].sub2]]+w[main_good[independent_ptr].main]+w[main_good[independent_ptr].sub1]+w[main_good[independent_ptr].sub2]);
}
}
cout<<f[independent_ptr][n];
}