GDKOI2021提高组Day2C抄写
1546+
作者：crxis 发布：2021-02-04 分类：字符串
题目大意：长度为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的回文中心去掉。
程序实现
