区间dp
题意：
给你长度为m的字符串，其中有n种字符，每种字符都有两个值，分别是插入这个字符的代价，删除这个字符的代价，让你求将原先给出的那串字符变成一个回文串的最小代价。
M<=2000
设 dp[i][j] 为区间 i~j 的回文串的最小代价
现在考虑怎样从别的状态转移到 区间i~j
三种情况
首先 str[i]==str[j] 那么 dp[i][j] = dp[i+1][j-1]
其次 (i+1)~j 是一个回文串 dp[i][j] = dp[i+1][j] + (add[str[i]] / del[str[i]])
最后 i~(j-1) 是一个回文串 dp[i][j] = dp[i][j-1] + (add[str[j]] / del[str[j]])
代码：
1 #include<cmath>
2 #include<cstdio>
3 #include<cstring>
4 #include<cstdlib>
5 #include<iostream>
6 #include<algorithm>
7 #define APART puts("----------------------")
8 #define debug 1
9 #define FILETEST 1
10 #define inf 2010
11 #define ll long long
12 #define ha 998244353
13 #define INF 0x7fffffff
14 #define INF_T 9223372036854775807
15 #define DEBUG printf("%s %d\n",__FUNCTION__,__LINE__)
16
17 namespace chino{
18
19 inline void setting(){
20 #if FILETEST
21 freopen("_test.in", "r", stdin);
22 freopen("_test.me.out", "w", stdout);
23 #endif
24 return;
25 }
26
27 inline int read(){
28 char c = getchar(), up = c; int num = 0;
29 for(; c < '0' || c > '9'; up = c, c = getchar());
30 for(; c >= '0' && c <= '9'; num = (num << 3) + (num << 1) + (c ^ '0'), c = getchar());
31 return up == '-' ? -num : num;
32 }
33
34 int n, m;
35 char s[inf];
36 int add[inf], del[inf];
37 int dp[inf][inf];
38
39 inline int main(){
40 n = read(), m = read();
41 scanf("%s", s + 1);
42 for(int i = 1; i <= n; i++){
43 char c = 0;
44 std::cin >> c;
45 add[c * 1] = read();
46 del[c * 1] = read();
47 }
48 int len = strlen(s + 1);
49 for(int i = 2; i <= len; i++){
50 dp[i][i] = 0;
51 for(int j = i - 1; j; j--){
52 dp[j][i] = INF;
53 if(s[i] == s[j])
54 dp[j][i] = dp[j + 1][i - 1];
55 dp[j][i] = std::min (dp[j][i] , dp[j + 1][i] + std::min (add[s[j] * 1], del[s[j] * 1]));
56 dp[j][i] = std::min (dp[j][i] , dp[j][i - 1] + std::min (add[s[i] * 1], del[s[i] * 1]));
57 }
58 }
59 printf("%d\n", dp[1][len]);
60 return 0;
61 }
62
63 }//namespace chino
64
65 int main(){return chino::main();}