0%

一类区间动态规划的优化 - 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)$?(根本不想分析复杂度。。。