ARC096D Sweet Alchemy
AtCoder Luogu 分析 考虑差分，则问题变为每次选择一棵子树，消耗 $\sum m_i$ 的材料，造出 $sz$ 个物品，且每棵不是原树的子树都只能选至多 $D$ 次。 令每棵子树的 $m_i$ 之和为其代价，$sz$ 为其收益，则相当于一个多重背包。 然而 $D$ 在 $10^9$ 级别，直接多重背包显然无法通过。 考虑一个错误的贪心：设 $w_i$ 为收益，$v_i$ 为代价，...
AtCoder Luogu 分析 考虑差分，则问题变为每次选择一棵子树，消耗 $\sum m_i$ 的材料，造出 $sz$ 个物品，且每棵不是原树的子树都只能选至多 $D$ 次。 令每棵子树的 $m_i$ 之和为其代价，$sz$ 为其收益，则相当于一个多重背包。 然而 $D$ 在 $10^9$ 级别，直接多重背包显然无法通过。 考虑一个错误的贪心：设 $w_i$ 为收益，$v_i$ 为代价，...