网站制作知识
[luoguP2890] [USACO07OPEN]便宜的回文Cheapest Palindrome(DP)
2025-01-03 14:13  点击:0

传送门

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