一类区间动态规划的优化 - Key Words

上周末 UESTC 校赛初赛，由于养老群里奇怪的爷爷一上来就开写这题还说挺好玩的，就看了下。

这是一个看上去是字符串的字符串题（雾

大致背景

给你一个长度为 $200$ 的回文串 $S$ ，一开始给你一个空串 $T$ ，你可以选择 $T$ 的一个位置，加一个特定的串 $S$ 进去。比如说 $S$ 是 aba，那么做了两次操作之后， $T$ 就可能是 aababa。

现在给你串 $T$ ，要你输出所有可能的 $S$ 。

第一反应，枚举子串，用区间 DP 判断是否可行。首先 $S$ 满足

• 长度能被 $T$ 的长度整除
• 是一个回文
• 是 $T$ 的一个子串

根据这三点，可以得到一个结论，不同的 $S$ 的个数最多只有 $L$ 个，这里 $L$ 是 $T$ 的长度。

然后嘛，当时第一反应 DP 状态是这个样子的

$$dp[l][r]$$

表示区间 $l$ 到 $r$ 是否可行。

这样的状态，转移应该是

$$dp[l][r] = \bigvee_{\substack{l' \leq l\\r' \geq r}}dp[l'][r']$$

这里 $l'$ 到 $l$ 还有 $r$ 到 $r'$ 这一段可以构成 $S$ 。

对于转移，如果是暴力的话，DP 的复杂度是 $O(N^4)$ 的，总体复杂度是 $O(N^5)$ ，内存的复杂是 $O(N^2)$ 。

考虑到时间复杂度有点高（嗯，只是一点啦），考虑把把 $S$ 的信息带到状态中去，我们定义状态

$$dp[l][r][i]$$

表示考虑到区间 $(l, r)$ ，我们最左边已经匹配完了 $S$ 的前 $i$ 个字符的方法是否可行。那么转移就是

$$dp[l][r][i] = dp[l + 1][r][i + 1] \lor \bigvee_{r' \geq r}\left(dp[l][r'][0] \land dp[r' + k][r][0]\right)$$

其中，要么匹配 $S$ 的当前位，要么把 $S$ 剩下的用右边匹配掉，这里 $k$ 是 $S$ 剩下的长度，这样转移复杂度是 $O(N)$ 的，总体复杂度是 $O(N^3)$ 。

这样总体复杂还算可以了（不过会 T 的吧大概，我猜的（。

回忆下 LCIS 的 DP，其实我们可以不需要枚举右边那段的位置，而让 DP 回来之后继续做 $(r', r' + k)$ 区间的匹配。定义状态

$$dp[i][j][k]$$

表示我们还要匹配 $i$ 个 $S$ 串，现在在 $T$ 的第 $j$ 位，在 $S$ 的第 $k$ 位，这个状态是否可行。注意我们有一个很强的条件，就是第一维和第三维的大小之积正好是 $N$ 。也就是说，这个状态是 $O(N^2)$ 的。

这样，对于转移我们可以在 $O(1)$ 时间内处理

$$dp[i][j][k] = dp[i][j - 1][k - 1] \lor \bigvee_{p}\left({dp[k][j][0] \land dp[i][j + p \times l][k]}\right)$$

其中 $l$ 是 $S$ 的长度， $p$ 是枚举的中间自匹配了多少个 $S$ ，总体的转移是 $O(\frac{L}{l})$ 的。

这样的话，整个 DP 的复杂度是 $O(N^2 \times \frac{L}{l})$ 的，总体复杂度会小于 $O(N^4)$ ？（根本不想分析复杂度。。。