contest link
题意:最小拼接代价,得到回文串。
题解一:将字符串翻转,原串、翻转串分别拼成一个常婵,最小化 $f_{tij}$,以原字符串 t 开始,$ij$ 分别指代原串、翻转串的匹配位置,匹配长度相同且过程中字符均相等的最小代价。统计答案时,$ij$ 均为字符串结尾,$j$ 为 $t$ 串翻转串结尾坐标。 $\text{状态数}<n*Len*Len$,暴力转移,$600ms/2s$ 飘过。
题解二:翻解题记录发现有 $5ms$ 解法比较奇妙,还在研究中