[ABC296Ex] Unite 题解

发布时间 2023-04-14 21:37:52作者: bykem

考虑状压 dp。

\(f_{i,j,s}\) 表示当前正在决策坐标为 \((i,j)\) 的格子,且列状态为 \(s\)。其中列状态维护了当前轮廓线上的连通块,我们可以使用最小表示法来简单维护。

(为什么不用广义括号序列?因为其涉及到 \(5\) 个可选值,由于 \(m\le 7\),所以这两个都需要用到八进制,而最小表示法显然要好写很多。)

如果我们选择将当前格子变成黑色,那么相当于合并了当前格上面和左边的两个连通块。

如果我们保持当前格子为白色,那么啥都不变,但要注意,这可能会导致某个连通块被孤立导致错解。

然后就没了?因为没有连通块被孤立,所以最后得到的一定是一个完整的连通块,直接统计答案即可。