BZOJ 1710 [Usaco2007 Open]Cheappal 廉价回文


题目链接: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 原来是因为交错题....

 

声明:zgz233|版权所有,违者必究|如未注明,均为原创|本网站采用BY-NC-SA协议进行授权

转载:转载请注明原文链接 - BZOJ 1710 [Usaco2007 Open]Cheappal 廉价回文


一个oier的博客 |注册功能过几天就修| 博客搬家啦,现在跑的飞快!

标签: , , ,