CF1767E Algebra Flash

Alex_Wei · 2022-12-18 10:27:30 · 题解

如果存在两个连续的平台未被激活，则不合法。

因此，存在相邻的颜色分别为 i 和 j 的平台，则在 (i, j) 之间连边。在 c_1 和 c_n 连自环，则问题转化为选择点权和最小的点集，使得每条边至少被一个点覆盖。根据经典结论，它等价于点权和减去最大权独立集。

最大权独立集有一个非常经典的做法：枚举前 n / 2 个点是否选择，对剩余 n / 2 个点的状态记忆化搜索即可。

相关资料：《浅谈信息学竞赛中的独立集问题》 - 学习笔记 - p_b_p_b。

时间复杂度 \mathcal{O}(n + 2 ^ {m / 2})，注意自环。代码。