[ABC319F] Fighter Takahashi
Atcoder：[ABC319F] Fighter Takahashi
洛谷：[ABC319F] Fighter Takahashi
Problem
一棵以 \(1\) 为根的 \(n\) 个节点的树，一个 otto 位于 \(1\) 号节点，其初始能力值为 \(1\)。
其余的每个节点 \(i\)，用三元组 \((t_i, s_i, g_i)\) 表示其信息：
-
若 \(t_i = 1\)，则该节点上有一只虚空卡比兽，其生命值为 \(s_i\)，如果 otto 的能力值不小于 \(s_i\)，则 otto 可以选择击掰这只虚空卡比兽，并使 otto 的能力值加 \(g_i\)。
-
若 \(t_i = 2\)，则该节点上有一个韭菜盒子，能够使 otto 的能力值乘上 \(g_i\)，并保证给出的 \(s_i = 0\)。
节点可以重复经过。问 otto 能否到达所有节点。
\(1 \le n \le 500, 0 \le m \le 10\)。
Solution
我的翻译显然是在犯贱，还请各位去看原题面。
一个显然的贪心策略是：如果当前还有不用药水能够击败的敌人，那一定是优先击败这个敌人，而不是去吃药水。
考虑在使用一个药水之前所有能击败的敌人，很显然击败他们的顺序是无关紧要的。也就是说，如果确定了 \(m\) 个药水的使用顺序，则击败的结果是确定的。
当已知药水的使用顺序时，我们可以采用 bfs 的思想，用优先队列决定当前能走到的未击败的敌人中生命值最低的是哪一个。
如果当前没有可以击败的敌人了，那就以确定的顺序服用一瓶药水，然后继续跑 bfs。
这样做的时间复杂度为 \(O(m!\times n\log{n})\)，数量级高达 \(10^{10}\)。
套路地，我们可以用状压 dp 优化枚举排列。记 \(f_S\) 表示已使用的药水集合为 \(S\) 时，能力值的最大值以及对应的遍历情况（具体即记哪些点已经被遍历。能这样做的正确性保证在于，如果 \(S\) 和能力值是确定的，则遍历情况也是确定的）。枚举下一个使用的药水是哪一个，实际上就是在逐步确定药水的使用顺序，但由于状压优化，那些不优的顺序在确定顺序的过程中就已经被 pass 掉了，不会在之后的转移中出现。
状态数 \(O(2^m)\)，枚举下一个药水 \(O(m)\)，转移 \(O(n\log{n})\)，总时间复杂度 \(O(nm2^m\log{n})\)。
注意能力值可能很大，但我们只需要将其与 \(10^9\) 取最小值，使其仍然能击败敌人即可。
这确实是一道有一定码量的 dp 好题。