为什么50分

感觉接近标算了啊。。。

思路：将每个主件及其附件打包成一组

然后分组背包DP

#include<bits/stdc++.h>
using namespace std;
int n,m,a[65][5],cnt;
int g[65],maxn;
int mon[65],wei[65];
int s[65],num[65];
int w[65][5];
int d[32005];
int ch[65][2];
void read(int& x)
{
    char c=getchar();
    x=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
}
int main()
{
    read(n);
    read(m);
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        read(x);
        read(y);
        read(z);
        if(z==0)
        {
            g[i]=++cnt;
            num[g[i]]=1;
            a[g[i]][1]=x;
            w[g[i]][1]=x*y;
        }
        else
        {
            ch[z][s[z]++]=i;
            mon[i]=x;
            wei[i]=mon[i]*y;
        }
    }
    for(int i=1;i<=m;i++)
    {
        if(ch[i][0]&&ch[i][1])
        {
            a[g[i]][2]=a[i][1]+mon[ch[i][0]]+mon[ch[i][1]];
            w[g[i]][2]=w[i][1]+wei[ch[i][0]]+wei[ch[i][1]];
            a[g[i]][3]=a[i][1]+mon[ch[i][0]];
            w[g[i]][3]=w[i][1]+wei[ch[i][0]];
            a[g[i]][4]=a[i][1]+mon[ch[i][1]];
            w[g[i]][4]=w[i][1]+wei[ch[i][1]];
            num[g[i]]=4;
        }
        else if(ch[i][0])
        {
            a[g[i]][2]=a[i][1]+mon[ch[i][0]];
            w[g[i]][2]=w[i][1]+wei[ch[i][0]];
            num[g[i]]=2;
        }
        else if(ch[i][1])
        {
            a[g[i]][2]=a[i][1]+mon[ch[i][1]];
            w[g[i]][2]=w[i][1]+wei[ch[i][1]];
            num[g[i]]=2;
        }
    }
    for(int i=1;i<=cnt;i++)
    {
        for(int j=n;j>=0;j--)
        {
            for(int k=1;k<=num[i];k++)
            {
                if(j>=a[i][k])
                d[j]=max(d[j],d[j-a[i][k]]+w[i][k]);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        maxn=max(maxn,d[i]);
    }
    printf("%d\n",maxn);
}
/*
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
*/