[NFLS 1459/6] 魔兽地图 题解

大意

给定若干物品, 一些物品可以直接购买, 不过有数量限制, 另一些物品需要若干其他的物品合成得到, 每个物品都有价值, 被合成消耗的物品不算价值, 给出购买的价钱限制, 求价值最大, 保证合成的方式构成森林.

题解

这题与其他的背包题不同的是, 需要分开来考虑用来用的和用来合成的, 需要加一个维度.

设 $f_{u, p, k}$ 为考虑到 $u$ 这个物品, $p$ 个用来合成, 花费 $k$ 的最大价值.
设 $q$ 为购买或者从下级合成而来的个数.

对于购买的物品:

$$f_{u, p, q \cdot cost_u} = val_u \cdot (q - p), \ p \le q \le lim_u$$

对于合成的物品:

$$f_{u, p, k} = max( (\sum_{v \in son(u), k = \sum k_v} f_{v, q \cdot cnt(v), k_v}) + val_u \cdot (q - p) , \ p \le q )$$

其中 $cnt(v)$ 表示合成 $u$ 需要 $cnt(v)$ 个物品 $v$.

合成的物品可以分别考虑需要的各个物品,
先枚举 $q$ , 再枚举 $v \in son(u)$.

$$g_{k} = \max_{0 \le k' \le k} g'_{k'} + f_{v, cnt(v)\cdot q, k - k'} \newline$$

$$f_{u, p, k} = \max\{f'_{u, p, k}, g_{k} + val_u \cdot (q - p)\} (p \le q) \newline$$