传送门
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