P11218 【MX-S4-T2】「yyOI R2」youyou 不喜欢夏天
算法
博弈类型的题
这个题属于最优解法的问题
最初可以看出 \(\rm{yy}\) 交换的列一定是一黑一白的, 不然无意义
考虑 \(\rm{youyou}\) 怎么选
对于两个都是黑的情况, 显然是都要选的, 这种贡献 yy 影响不了
对于两个都是白的情况, 显然是只选一个, 最大化贡献
对于一白一黑的情况, 有以下两种情况
- 选两个
- 选一个黑
对于选两个, \(\rm{yy}\) 无事可做
对于选一个黑, \(\rm{yy}\) 显然可通过交换使贡献 \(-2\)
那么考虑两种情况分讨
对于所有一黑一白都选, 那么答案是显然可以 \(O(n)\) 根据连通性求最优
对于选一个黑, 这里有一个 \(\rm{trick}\)
令所有都选一黑一白, 用 \(f_{i, j}, j \in {0, 1, 2}\) 表示考虑连通块的右端点以 \(i\) 结尾，且 \(i\) 这一列只选上/只选下/上下都选
可以 \(O(n)\) 计算, 在最后减去 \(2 \times m\) 即可, 这有可能不是真实的结果, 但是只要你选 \(< m\) 列黑白的他一定是不优的，所以劣的情况都不会被统计到。
代码
略
总结
对于最优策略类题目, 不一定要算出准确的结果, 只要保证正确性即可