[luoguP2890] [USACO07OPEN]便宜的回文Cheapest Palindrome（DP）

传送门

f[i][j] 表示区间 i 到 j 变为回文串所需最小费用

1.s[i] == s[j]　　f[i][j] = f[i + 1][j 1]

2.s[i] != s[j]　　f[i][j] = min(f[i + 1][j] + cost[s[i]], f[i][j 1] + cost[s[j]])

开头去掉一个字母和结尾增加一个字母的效果是一样的

所以 cost[s[i]] = min(add[s[i]], del[s[i]])

——代码

1 #include <cstdio> 2 #include <cstring> 3 #include <iostream> 4 5 int n, m; 6 int a[301], f[2010][2010]; 7 char s[2010]; 8 9 inline int read() 10 17 18 inline int min(int x, int y) 19 22 23 inline int dp(int x, int y) 24 30 31 int main() 32 43 memset(f, 1, sizeof(f)); 44 printf("%d\n", dp(1, m)); 45 return 0; 46 }
View Code

上一篇：高精度

下一篇：[luoguP1433] 吃奶酪（DP || Dfs）

---

DP