简要题意
翻译很清楚。
思路
记 \(x_i\) 表示第 \(i\) 个人的花费,\(s_i\) 表示第 \(i\) 个人做题集合,\(k_i\) 表示第 \(i\) 个人需要的显示器。
\(m \le 20\) 且不是计数,考虑 dp
,发现确实可以做。
可以设 \(f_i\) 表示做题集合为 \(i\) 时最小花费。
易得状态转移:
\[f_{i\cup s_i} = \min\{f_j +x _i + t \times b\} \]\(t\) 表示需要新买的显示器。特别的,不需要购买时 \(t = 0\)
但是这样做不对,因为对于 \(x_i + k _ i \times b = x_j +k_j \times b\) 时,可能会选择 \(k_i\) 更小的那个人,那么就要再将 \(k\) 从大到小排序,因为这样能让后面花费在显示器上的钱尽量小。
标签:显示器,题解,texttt,times,Gena,Cunning From: https://www.cnblogs.com/zdrj/p/18130052