```cpp
#include<bits/stdc++.h>
#define N 65
using namespace std;
inline int cinn(){
int x=0,w=0; char ch=0;
while(!isdigit(ch)){w|=ch=='-';ch=getchar();}
while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48), ch=getchar();
return w?-x:x;
}
int m,n,ip[N],cnt,a[N][30],w[N],v[N],fa[N],f[N][100005];
int main(){
n=cinn();m=cinn();
for(int i=1;i<=m;i++){
w[i]=cinn();
v[i]=cinn();
fa[i]=cinn();
if(fa[i]==0){
a[++cnt][1]=i;
ip[i]=cnt;
}
else{
a[ip[fa[i]]][0]++;
a[ip[fa[i]]][a[ip[fa[i]]][0]+1]=i;
}
}
for(int i=1;i<=cnt;i++)
for(int j=1;j<=n;j++){
f[i][j]=f[i-1][j];
if(j>=w[a[i][1]])
f[i][j]=max(f[i-1][j],f[i-1][j-w[a[i][1]]]+w[a[i][1]]*v[a[i][1]]);
if(a[i][0]==1){
if(j>=w[a[i][1]]+w[a[i][2]])
f[i][j]=max(f[i][j],f[i-1][j-w[a[i][1]]-w[a[i][2]]]+w[a[i][1]]*v[a[i][1]]+w[a[i][2]]*v[a[i][2]]);
}
if(a[i][0]==2){
if(j>=w[a[i][1]]+w[a[i][3]])
f[i][j]=max(f[i][j],f[i-1][j-w[a[i][1]]-w[a[i][3]]]+w[a[i][1]]*v[a[i][1]]+w[a[i][3]]*v[a[i][3]]);
if(j>=w[a[i][1]]+w[a[i][3]]+w[a[i][2]])
f[i][j]=max(f[i][j],f[i-1][j-w[a[i][1]]-w[a[i][2]]-w[a[i][3]]]+w[a[i][1]]*v[a[i][1]]+w[a[i][2]]*v[a[i][2]]+w[a[i][3]]*v[a[i][3]]);
}
}
cout<<f[cnt][n]<<endl;
return 0;
}
```
by geother @ 2019-02-10 14:33:46
思路我来回想了将近十遍 应该没错```
```cpp
就是对于每个主件dp
有五种情况
1 用这个主件
2 不用这个主件
3 用主件+附件1
4 用主件+附件2
5 用主件+附件1+附件2
```
难道这个思路不对
求大佬指正
by geother @ 2019-02-10 14:38:21
思路是可行的，应该是细节上有小问题
by AC_Automation @ 2019-02-10 15:23:24
您的`for(int j=1;j<=n;j++)`应该改为`for(int j=n;j>=1;j--)`，前者是完全背包
by fenggwsx @ 2021-11-03 22:34:22