P2238 题解

problem & blog。

kkk 的题解有一些地方是错的 /cf，所以写篇题解造福后人。

一眼 DP，如果你平凡地设 \(dp_{i,j}\)，会发现买过的是不能再买的，然后就转移不动了。所以要记录每个点附近的点是否被吃过。

于是状压，每个二进制位表示 \((i,j)\) 周围的一些点是否被吃过。不妨钦定 \(X\) 表示当前位置，\(Y\) 表示下一步的位置。

若往右走，\(Y\) 的左面必定吃过，下边必定没吃过。然而，\(Y\) 的右面与上面不知道是否吃过（即如果吃过的话，这一位状态就是固定的）；往下走时，\(Y\) 的上面必定吃过，右面必定没吃过，\(Y\) 的左面不知道是否吃过。

所以枚举 \(X\) 时，我们还得提前知道 \(Y\) 的其中两面是否被吃过。于是状压需要记录：右，下，右上（即往右走时 \(Y\) 的上面），左下（即往下走时 \(Y\) 的左面）是否吃过。

考虑转移，以往右走为例，往下走是同理的。首先 \(Y\) 一定没有被吃过，其次 \(Y\) 的上、下、右至少要有 \(2\) 个位置没有被吃过。转移的话看右、下、右上三位，还有就吃掉，非常简单。

于是做完了，代码很好写。一些小细节：

• 有些东西没有表示出来，如往右走时 \(Y\) 的上面，其实就是 \(X\) 的右上；往右走时 \(Y\) 自己的状态，就是 \(X\) 的右面。
• 有一些东西必须相等，如往右走时 \(X\) 的下面和 \(Y\) 的左下是同一个东西。

code，时间复杂度 \(O(nmT^2)\)，\(T=2^4\)。