场上只切了 4 题怎么办/ll要不要退役/ll
Difficulty:4.8(蓝题下位)/ Easy+
Tag:DP 套 DP(?
首先考虑爆搜。但这是指数级,太不牛了。
考虑用状态代替被搜索的串,使得最后有一种简单的方法判定状态。
显然我们可以记录当前前缀可以被表示为哪些 xyxxy...xyxxy...xyxxy... 之类和最后 x/yx/yx/y 的前 iii 位字符拼接。状态太多了!注意到只有最后的那个前缀字符才是真正被用到的,其它都可以抛弃。这样可能的状态数量就只有 ∣X∣+∣Y∣≤16|X|+|Y|\le 16∣X∣+∣Y∣≤16 了,但是显然一个字符串可以用若干个这种状态表示,所以用 O(2∣X∣+∣Y∣)O(2^{|X|+|Y|})O(2∣X∣+∣Y∣) 个二进制状态记录每一种状态是否存在,转移时最后判断状态中是否存在一个完整的 XXX 或一个完整的 YYY 即可。
然后我们发现可以把相同长度相同状态压成一种一起转移,显然是对的。
预处理每一种状态下一位接 0/10/10/1 会变为哪些状态。然后接个 DP 即可做到 O(∣S∣×2∣X∣+∣Y∣)O(|S|\times 2^{|X|+|Y|})O(∣S∣×2∣X∣+∣Y∣),可以通过。
代码中使用了滚动数组减小空间。