StringPath

作者：杨景钦

关键词：轮廓线动态规划 状态压缩 暴力

题目描述

有一个$n \times m$的棋盘， 每个格子上有一个大写字母， 你可以从左上角$(1,1)$出发， 每次只能向下走或者向右走， 走到$(n, m)$。 你走过的路径上的字符顺次相接， 就得到了这个路径对应的字符串。

现在给你两个不同的长为$n + m - 1$的字符串， 已知对于每个给出的字符串， 这个棋盘都存在一条从$(1,1)$到$(n, m)$的路径，使得这条路径对应的字符串， 就是这个字符串。

问有多少种不同的满足条件的棋盘。 两个棋盘不同当且仅当存在某个格子上的字母不同。

$1 \leq n, m \leq 8$

算法一

首先考虑只有一个字符串怎么做。

观察每条路径， 事实上我们可以把棋盘顺时针旋转$45$度， 这样任意一条路径的第$i$个格子， 就在新棋盘的第$i$行。

考虑对于新棋盘按照从上往下从左到右的顺序进行轮廓线动态规划， 令$dp[x][y][mask]$表示当前已经填到第$x$行的第$y$个格子， 轮廓线上的格子状态为$mask$的方案数。

这里的$mask$每一位存的是， 是否存在一条从$(1,1)$到这个格子的路径， 满足前面的字符与给出的字符串相同。

转移十分显然， 只需要枚举当前这个格子是否和给出的字符串的第$x$个字符一样即可。

复杂度$O(N \times M \times 2^{max(N, M)})$

这里虽然是两个字符串， 事实上是类似的。 只需要存两个$mask$分别表示两个字符串的状态即可。 当然也可以只用一个$mask$

复杂度$O(N \times M \times 4 ^ {max(N, M)})$