用户工具

站点工具


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$卡过,有$5ms$解法比较奇妙还在研究中

2020-2021/teams/looking_up_at_the_starry_sky/shenzhonghai/atcoder_beginner_contest_175.1598001642.txt.gz · 最后更改: 2020/08/21 17:20 由 x342333349