BZOJ 3790 神奇项链

发布于 2018-01-26  191 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3790

题意:有两个机器,第一个可以制作任意回文串,第二个可以拼接两个回文串,并且可以去掉前后缀的重叠部分,问得到给定串的最少二机器使用次数。


考虑处理出每个下标 i 向右最长延伸的回文串长度\(r_i\),即用一些线段可重的覆盖线段。

这个过程 \(O(n)\) 的贪心即可,在满足左端点的情况下右端点越远越好。

对于处理 \(r_i\) 数组,可以用回文自动机,即在每次插入一个字符后用 \(len_{last}\) 去更新 \(r_{n-len[last]+1}\)。

 


一个非常弱的准退役OIER