BZOJ 1710 [Usaco2007 Open]Cheappal 廉价回文

发布于 2017-06-14  165 次阅读


题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1710

题意:对于每个字符添加和删除都有一个费用,求将一个给定串修改为回文串的最小费用....


对于最终结果而言,添加一个字符和在对称位置删除一个字符是没有区别的,这样就干掉了添加操作,费用取 min 即可

于是 dp \(f_{i,j}\) 表示将 [i,j] 区间修改为回文串的最小费用 显然\(f_{i,j}=min(f_{i+1,j}+cost_{a_i},f_{i,j-1}+cost_{a_j})\)

当\(a_i=a_j\) 时\(f_{i,j}\) 和\(f_{i+1,j-1}\) 取一个 min 即可

又 WA 又 RE 原来是因为交错题....

 


一个非常弱的准退役OIER