【Nowcoder17062】回文


题意

每次可以删除头部或者尾部的一个字母\(x\),代价为\(a_x\);

每次可以在头部或者尾部新增一个字母\(x\),代价为\(b_x\)。

求最小代价,使其变成回文串。

分析

对于每一个位置,用 Manacher 处理出最长的回文串,剩下问题就是处理旁边剩余的两串字符串花费最小代价变成回文串。

显然,肯定会删除其中一边的所有字母,另一边的字母就是保留一部分。

对于删除的一边,前缀和处理一下即可。

另一边,考虑保留的一定是靠内的一段,因为无法做到从保留的字母中间删除字母,考虑dp预处理。

最后枚举所有的位置所延伸出的回文串以及处理的代价即可。

 

You may also like

【TJOI2015】弦论

【AHOI2013】差异

LEAVE A COMMENT

Statistics

  • 0
  • 8,090

Categories

Archive

Comments