好久没做背包的题了，有点生，回去刷几道水题找找感觉，又遇到了这道金明的预算方案
还是原来的配方还是原来的味道。本来以为附件数目不限，结果发现至多两个，索性不改了，接着写下去。
老规矩，先放题面

题目描述

金明今天很开心，家里购置的新房就要领钥匙了，新房里有一间金明自己专用的很宽敞的房间。更让他高兴的是，妈妈昨天对他说：“你的房间需要购买哪些物品，怎么布置，你说了算，只要不超过\(N\)元钱就行”。今天一早，金明就开始做预算了，他把想买的物品分为两类：主件与附件，附件是从属于某个主件的，下表就是一些主件与附件的例子：
主件 附件
电脑 打印机，扫描仪
书柜 图书
书桌 台灯，文具
工作椅 无
如果要买归类为附件的物品，必须先买该附件所属的主件。每个主件可以有\(0\)个、\(1\)个或\(2\)个附件。附件不再有从属于自己的附件。金明想买的东西很多，肯定会超过妈妈限定的\(N\)元。于是，他把每件物品规定了一个重要度，分为\(5\)等：用整数\(1-5\)表示，第\(5\)等最重要。他还从因特网上查到了每件物品的价格（都是\(10\)元的整数倍）。他希望在不超过\(N\)元（可以等于\(N\)元）的前提下，使每件物品的价格与重要度的乘积的总和最大。
设第\(j\)件物品的价格为\(v[j]\)，重要度为\(w[j]\)，共选中了\(k\)件物品，编号依次为\(j_1,j_2,…,j_k\)，则所求的总和为：
\(v_[j_1] \times w_[j_1]+v_[j_2] \times w_[j_2]+ …+v_[j_k] \times w_[j_k]\)。
请你帮助金明设计一个满足要求的购物单。

输入输出格式

输入格式：

第 \(1\) 行，为两个正整数，用一个空格隔开：
\(N m\) （其中 \(N(<32000)\) 表示总钱数， \(m(<60)\) 为希望购买物品的个数。） 从第 \(2\) 行到第 \(m+1\) 行，第\(j\)行给出了编号为\(j−1\)的物品的基本数据，每行有\(3\)个非负整数\(v p q\) （其中 v 表示该物品的价格（ \(v<10000\) ），p表示该物品的重要度\(（1-5）\)，\(q\)表示该物品是主件还是附件。如果\(q=0\)，表示该物品为主件，如果\(q>0\)，表示该物品为附件， \(q\) 是所属主件的编号

输出格式：

一个正整数，为不超过总钱数的物品的价格与重要度乘积的总和的最大值（\(<200000\)）。

输入输出样例

输入样例：

1000 5
800 2 0
400 5 1
300 5 1
400 3 0
500 2 0

输出样例：

2200

思路很简单，配件不单独拿出来，我们只处理主件，配件绑定主件处理。

那么对于每一个主件\(i\)和它的两个配件\(j，k\)，一共有五种情况，分别是：

1.一个也不选

2.只选择主件\(i\)

3.选择主件\(i\)和附件\(j\)

4.选择主件\(i\)和附件\(k\)

5.选择主件\(i\)以及附件\(j，k\)

那么状态转移方程也就出来了，我们用w数组表示价值，v数组表示体积,用\(m\)表示背包当前容积，也就是

\(f[m]=max(f[m],f[m-v[i]]+w[i],f[m-v[i]-v[j]]+w[i]+w[j],f[m-v[i]-v[k]]+w[i]+w[k],f[m-v[i]-v[j]-v[k]]+w[i]+w[j]+w[k])\)

要注意的是，本题有两个可以优化的点，一是每件物品的价格都是整十，那么如果m非整十，那么它非整十的部分也无法利用，那么我们就把每件物品的体积还有背包总容积都除以\(10\)，输出的时候再乘十即可。第二个点就是重要度在输入的时候直接乘到价值上即可

上代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#define ll long long
#define gc() getchar()
#define maxn 65
#define maxm 20005
using namespace std;

inline ll read(){    //日常读入优化，对这道题毫无卵用
    ll a=0;int f=0;char p=gc();
    while(!isdigit(p)){f|=p=='-';p=gc();}
    while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
    return f?-a:a;
}
void write(ll a){
    if(a>9)write(a/10);
    putchar(a%10+'0');
}

int n,m,v[maxn],w[maxn],f[maxm],c[maxn][maxn];  //c[i][0]表示主件为i的物品的数量，那么c[0][0]就表示主件的数量，c[i][j]表示主件为i的第j个物品的标号，这样写本意是处理无穷个配件，结果发现配件至多有两个，懒得改了
int main(){
    m=read()/10;n=read();
    for(int i=1;i<=n;++i){
        v[i]=read()/10;w[i]=read()*v[i];
        int q=read();c[q][++c[q][0]]=i;
    }
    for(int i=1;i<=c[0][0];++i)
        for(int k=m;k>=v[i];--k)
            f[k]=max(f[k],max(max((k-v[c[0][i]])>=0?f[k-v[c[0][i]]]+w[c[0][i]]:0,(k-v[c[0][i]]-v[c[c[0][i]][1]])>=0?f[k-v[c[0][i]]-v[c[c[0][i]][1]]]+w[c[0][i]]+w[c[c[0][i]][1]]:0),max((k-v[c[0][i]]-v[c[c[0][i]][2]])>=0?f[k-v[c[0][i]]-v[c[c[0][i]][2]]]+w[c[0][i]]+w[c[c[0][i]][2]]:0,(k-v[c[0][i]]-v[c[c[0][i]][1]]-v[c[c[0][i]][2]])>=0?f[k-v[c[0][i]]-v[c[c[0][i]][1]]-v[c[c[0][i]][2]]]+w[c[0][i]]+w[c[c[0][i]][1]]+w[c[c[0][i]][2]]:0)));  //表面上这个地方很复杂，实际上原理很简单，就是上面我们所说的5种情况
    write(f[m]*10);
    return 0;
}