当前位置:首页 > 字符串 > 正文
GDKOI2021提高组Day2C抄写
1050+

题目大意:长度为n的字符串,可以逐个字母抄写,字母i的费用为$v_i$,也可以通过折叠将以末尾为中心的对称字符串印到后面去,费用为m,请问得到这个字符串的最小费用是多少?

解题思路

定义状态f[i]表示得到长度为i的字符串的最小费用,如果不复制,那么f[i] = f[i-1] + v[s[i;如果复制,那么可以在前面找对称中心j,f[i] = f[j] + m,j有很多个,取费用最小的即可。当然,这个回文中心j最远扩展的位置要包含i才可以。因此,我们可以用Manacher算法预处理出每个以每个位置(包括空隙)为中心的回文串边界,用单调队列或者优先队列维护最优值位置j,并将过期的、边界不包含i的回文中心去掉。

程序实现

GDKOI2021提高组Day2C抄写:等您坐沙发呢!

发表评论

您必须 [ 登录 ] 才能发表留言!