1 条题解
-
0
- 1
信息
- ID
- 194
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 4
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者
一共只有 3 个点,手动讨论两个人的选择情况,时间复杂度为 O(1)。
考虑 f[S][T] 表示 Alice 目前把 S 集合染成了黑色,Bob 目前把 T 集合染成了白色两人采取最优策略的最终答案。
如果为 Alice 的回合,一定选所有后继状态中的最大值,如果为 Bob 的回合,一定选后继状态的最小值,每个点只有黑色/白色或还未被染色,时间复杂度不超过 O(3n)。
如果一条边最终不是黑边也不是白边,我们看成两人分别得到了这条边边权的一半。
所以把每个点的点权看作所有邻边的边权之和的一半,按照点权两人从大到小依次取即为最优策略。