购物清单 II

题目描述

小明的购物清单升级了！现在他面对的是更复杂的促销活动。

小明的预算上限依然为 $M$ 元。商城里有 $N$ 个产品包，物品之间的依赖关系如下：

• 有些产品是“主件”，可以直接购买。
• 有些产品是“附件”，必须在购买了对应的主件后，才能购买该附件。
• 在本题中，每个主件最多有两个附件。

每件产品（无论是主件还是附件）的属性如下：

• 价格 $w_i$。
• 魅力值 $v_i$。
• 如果是一件附件，它会指明所属主件的编号；如果是主件，则该项为 0。

请计算小明在不超过预算的前提下，通过合理搭配主件和附件，能够获得的最大魅力值总和。

输入格式

第一行包含两个整数 $M$ 和 $N$，分别表示总预算和总产品数。

接下来的 $N$ 行，每行包含三个整数 $w_i, v_i, p_i$，分别表示价格、门魅力值以及所属主件编号。

• 如果 $p_i = 0$，表示该产品是主件。
• 如果 $p_i > 0$，表示该产品是第 $p_i$ 个产品（即输入中的第 $p_i$ 行）的附件。

输出格式

输出一个整数，表示在预算范围内能获得的最大魅力值总和。

输入输出样例 #1

输入 #1

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

输出 #1

12

样例 1 说明

预算 1000：

• 方案 1：买主件 2 + 附件 3（重 400+300=700，价值 5+5=10）。
• 方案 2：买主件 2 + 附件 5（重 400+500=900，价值 5+2=7）。
• 方案 3：买主件 4 + 附件 3（不行，3 是 2 的附件）。
• 方案 4：买主件 2 + 附件 3 + 附件 5（重 400+300+500=1200，超预算）。
• 方案 5：买主件 2 + 附件 3 + 主件 4（不行，400+300+400=1100，超预算）。 注意：附件只能在买了主件后买。在此样例中，最优可能是其他组合。 （注：样例中的 $v_i$ 是为了演示，实际题目中 $v_i$ 可能较大）。

数据范围

对于 $100\%$ 的数据，$1 \le M \le 32000$，$1 \le N \le 60$，$w_i$ 为 10 的整数倍，$v_i$ 为 $1 \sim 5$ 之间的整数。 （注：为了贴合经典模型，建议将魅力值定义为 $w_i \times \text{重要度}$，输出最大总和）。 修正：为了计算方便，直接给出价格 $w_i$ 和魅力值 $v_i$。数据范围 $M \le 32000$，$N \le 60$，$w_i, v_i \le 10000$。

建议

三刷