字符串游戏

Source and Judge

bzoj2121

Record

2h

Analysis

请先思考后再展开

因为删除的都是序列,比较难思考,不妨想成删除一段区间中没被删除的部分,那么区间是个dag
设 f(l,r,a,b)表示原串l到r,最后匹配第a个字符串(即l和r都是a的)的第b个字符
然后为了方便转移,设v(l,r)表示能否删除
转移显然,时间复杂度为 $O(L^3ab)$ 理论上是跑不满的,所以注意一些显然的优化即可

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/f9d8.html
转载请注明出处,谢谢!

哪怕是一杯奶茶,也将鼓励我继续创作!
0%