ABC424D

· · 题解

赛时写贪心假完了。这么唐的状压都不会，感觉这辈子有了。

这种题无非状压 / 神秘搜索。状压显然更好想更好写。考虑状压。F_{i,S} 表示前 i 行，当前行状态为 S 的最小代价。其余就是板子转移即可。

我的实现是 \mathcal{O(n^22^{2n})} 的，肯定能继续优化。具体就是对于上下两行，预处理出合法的状态，这样能优化掉一个 n。过了就扔了。

Submission