P1064 题解报告
题目链接
首先我们针对于每一件物品我们定义其 价值 为 ci=wi×vic_i=w_i \times v_ici =wi ×vi 。
其次针对于每一组物品，我们有以下五种选择：
1. 只买主件
2. 买主机加附件 1
3. 买主件加附件 2
4. 全买
5. 都不买
以上五种选择对应的代价和价值是（此处我们令当前这组主件为 mcmcmc，附件 1 为 c1c_1c1 ，附件 2 为 c2c_2c2 ）：
编号 购买情况 代价 价值 1 只买主件 vmcv_{mc}vmc wmcw_{mc}wmc 2 买主机加附件 1 vmc+vc1v_{mc}+v_{c_1}vmc +vc1 wmc+wc1w_{mc}+w_{c_1}wmc +wc1 3 买主件加附件 2 vmc+vc2v_{mc}+v_{c_2}vmc +vc2 wmc+wc2w_{mc}+w_{c_2}wmc +wc2 4 全买 vmc+vc1+vc2v_{mc}+v_{c_1}+v_{c_2}vmc +vc1 +vc2 wmc+wc1+wc2w_{mc}+w_{c_1}+w_{c_2}wmc +wc1 +wc2 5 都不买 000
000
然后考虑存储问题，不妨定义一个二维数组 ccc，其中第一维度存储主件，第二维度存储附件。
其中第 iii 维度下标为 111 的元素表示第 iii 个物品的第 111 个附件，同理，第 iii 维度下标为 222 的元素表示第 iii 个物品的第 222 个附件，特别地，为了存储每个主件分别有多少个附件，我们定义第 iii 维度下标为 000 的元素 ci,0c_{i,0}ci,0 表示第 iii 个物品有 ci,0c_{i,0}ci,0 个附件（显然，如果第 iii 个物品为附件，那么 ci,0c_{i,0}ci,0 一定为 000），且所有主件均属于编号为 000 的物品的附件。
为了方便理解，接下来我们用样例来举例二维数组 ccc 的存储情况。
表头 0 1 2 3 0 333 111 444 555 1 222 222 333 空 2 000 空 空 空 3 000 空 空 空 4 000 空 空 空 5 000 空 空 空
见上，c0,0c_{0,0}c0,0 表示一共有 333 个主件，c1,0c_{1,0}c1,0 表示第 111 个物品一共有 222 个附件，其中第 222 个附件（即 c1,2c_{1,2}c1,2 ）是编号为 333 的物品。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
最后我们只需将每组看做一个物品跑个采药（即 P1048）即可：
推销同类题
