解题思路
题目是集合覆盖:每台机器提供一个条目集合,要覆盖业务点名的 t 条,并让启用台数最小;无解输出 0。d≤30、t≤20,不能枚举 2d 台机器子集,但可以对「已经覆盖了哪些业务条目」做状压。
- 给业务点名的 t 条互异编号映射到比特 0..t−1。每台机器只保留落在这 t 条上的条目,得到覆盖掩码 c。与业务无关的编号直接丢掉。
- 设 dp[s] 为覆盖集合恰好等于 s 时的最少台数,初值 dp[0]=0,其余为正无穷。按机器做 0-1 转移:倒序枚举旧集合 s,用 dp[s]+1 去更新 dp[s∣c],保证每台最多用一次。
- 全集 full=(1<<t)−1。若 dp[full] 仍是无穷,说明有条目从未出现,答案为 0;否则就是最少台数。
- 常见假解:按「当前还能新覆盖多少」贪心(会多选)、无解时输出 −1、把条目编号当成 1..t 而不做映射、三重循环枚举机器子集 O(2d)。