CSP-S 考前做题

P11218

首先还是博弈论题要么打表找规律要么dp。

然后注意到 \(2 \times n\) 网格这个东西非常典，状态数很少，可以状压。

首先我们做一点观察：不难发现 \(1 1\) 一定全选， \(0 0\) 可以选一个，然后 \(0 1\) 可以选两个然后没贡献，这样他就没法换，跑一遍最大子段和。

然后注意到他换只能换 \(0 1\) 。

如果你选了一些 \(0 1\), 那他一定会给你定点爆破，把那些 \(0 1\) 换了，你损失 \(2 \times m\) 答案。

然后注意到你如果 \(0 1\) 选 \(1\) 的个数很多的话那你可以选，但是 $ < 2 \times m$ 列肯定不优，不妨把 \(2 \times m\) 拿出来，然后你现在就相当于选一个联通块，然后你要最大化 1 个数 - 0 个数。

然后注意到 \(2 \times n\) 网格这个东西非常典，状态数很少，可以状压。

然后设 \(f_{i,S}\) 表示 以 \(i\) 结尾状态 \(S\) 就做完了。

code

我自己想的时候到选联通块那一步把问题错误的转化成了最大子段和，然后发现是假的，后来没想到怎么刻画联通块。建议重新审视问题。