2023-02-18

题目传送门

翻译

难度&重要性(1~10):5

题目来源

AtCoder

状压dp

我们令 \(S\) 表示当前箱子状态，\(P_i\) 表示第 \(i\) 把钥匙能开的箱子。

设 \(f_S\) 表示开启当前状态箱子的最小花费。

能得到转移方程:

\(f_{P_i|i}=\min(f_{P_i|i},f_i+a_i)\)

时间复杂度 \(O(2^nnm)\)，实际可以优化到 \(O(2^nm)\)。

已完成