做题记录 25.8.31
szt100309
·
·
个人记录
QOJ #6331. Jewel Game
令 f_{s,a,b} 表示子集 s 中的 \text{jewel} 没有使用过，目前先手在 a，后手在 b，最大的分数，令 w_u 表示点 u 上的 jewel 的权值（不存在则为 0），令 id_c 为 c 点的 jewel 的 id（不存在则值为任意一个一定不在 s 中的值），显然转移为
f_{s,a,b}=\max_{(a,c)}(w_c-f_{s/\{id_c\},b,c})
按 s 从大到小 dp，s 相同的，重复迭代以上过程直到 f_s 不变，显然迭代次数不超过 O(n)，因此时间复杂度 O(2^kn^2m)
代码
参考
存在 O(2^k n(n+m)\log n) 的算法