poj 3280 Cheapest Palindrome (区间dp)

poj 3280 题目链接

题意:一个字符串,给出添加一个字符或者删掉该字符的花费,问最小的话费使得字符串变成回文串。

思路:dp[i][j]表示区间[i,j]的字符串变成回文的最小花费。。。

这个可以想到。。dp[i][j] = dp[i+1][j-1] (a[i]==a[j])这个也可以想到。。。

增加和删除是等价的,所以取小的那个代价就行。。这个我也想到了。。

然后转移的地方没有特别明白。。。

和之前的找到一个划分的点k不同的是。。。

如果不等于。。

那么

这个方程可以理解。。。但是感觉自己想不出来 QAQ

以及。。我初始化写错了。。。

以为是求 最小值就初始化成了0x3f…

但是这样是错的。。。

具体见代码注释。。。

 

作者: CrazyKK

ex-ACMer@hust,researcher@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz