菜王的 blog

提供一个无脑 bitset 优化暴力 DP 的做法。

首先如果 $n + m$ 为偶数则无解。

然后可以想到一个朴素的 DP：设 $f_{i, j, k}$ 为是否存在从左上角到 $(i, j)$ 且经过 $k$ 个 $1$ 的路径，转移简单不讲。

这个 DP 的 $k$ 只需要枚举到 $(n + m - 1) / 2$ 的范围，所以时间复杂度为 $O(nm(n + m))$，常数大概为 $1/2$。

然后这个 DP 很明显可以用 bitset 优化，时间复杂度变为 $O(\dfrac{nm(n + m)}w)$，$w$ 取 $32$ 或 $64$，我们就得到了一个非常小的常数。

然后呢？然后就冲过去了。