用户工具

站点工具


2020-2021:teams:looking_up_at_the_starry_sky:shenzhonghai:atcoder_beginner_contest_175

contest link

F

题意:最小拼接代价,得到回文串。

题解一:将字符串翻转,原串、翻转串分别拼成一个常婵,最小化 $f_{tij}$,以原字符串 t 开始,$ij$ 分别指代原串、翻转串的匹配位置,匹配长度相同且过程中字符均相等的最小代价。统计答案时,$ij$ 均为字符串结尾,$j$ 为 $t$ 串翻转串结尾坐标。
$\text{状态数}<n*Len*Len$,暴力转移,$600ms/2s$ 飘过。

题解二:翻解题记录发现有 $5ms$ 解法比较奇妙,还在研究中

2020-2021/teams/looking_up_at_the_starry_sky/shenzhonghai/atcoder_beginner_contest_175.txt · 最后更改: 2020/09/14 11:28 由 x342333349