传送门
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
上一篇：[luoguP2763] 试题库问题（最大流）
下一篇：[luoguP2870] [USACO07DEC]最佳牛线，黄金Best Cow Line, Gold（后缀数组）
DP
