POJ-3280 Cheapest Palindrome---区间DP

题目链接：

https://vjudge.net/problem/POJ-3280

题目大意：

给出一个由m中字母组成的长度为n的串，给出m种字母添加和删除花费的代价，求让给出的串变成回文串的代价。

思路：

区间DP，

我们知道求添加最少的字母让其回文是经典dp问题，转化成LCS求解。这个是一个很明显的区间dp

我们定义dp [ i ] [ j ] 为区间 i 到 j 变成回文的最小代价。

那么对于dp【i】【j】有三种情况

首先：对于一个串如果s【i】==s【j】，那么dp【i】【j】=dp【i+1】【j-1】

其次：如果dp【i+1】【j】是回文串，那么dp【i】【j】=dp【i+1】【j】+min（add【i】，del【i】）；

最后，如果dp【i】【j-1】是回文串，那么dp【i】【j】=dp【i】【j-1】 + min（add【j】，del【j】）；

 1 #include<iostream>
 2 #include<cstring>
 3 using namespace std;
 4 const int INF = 0x3f3f3f3f;
 5 const int maxn = 2000 + 10;
 6 int n, m;
 7 int dp[maxn][maxn];
 8 struct node
 9 {
10     int del, add;
11 };
12 node a[30];
13 int main()
14 {
15     cin >> n >> m;
16     string s;
17     cin >> s;
18     int x, y;
19     char c;
20     for(int i = 0; i < n; i++)
21     {
22         cin >> c >> x >> y;
23         a[c - 'a'].add = x;
24         a[c - 'a'].del = y;
25     }
26     memset(dp, INF, sizeof(dp));
27     for(int i = 0; i < m; i++)dp[i][i] = 0;
28     for(int len = 1; len < m; len++)
29     {
30         for(int start = 0; start + len < m; start++)
31         {
32             int end = start + len;
33             int x = s[start] - 'a';//起点的字母
34             int y = s[end] - 'a';//终点的字母
35             dp[start][end] = INF;
36             if(s[start] == s[end])
37             {
38                 if(start + 1 <= end - 1)dp[start][end] = dp[start + 1][end - 1];
39                 else dp[start][end] = 0;
40             }
41             else
42             {
43                 dp[start][end] = min(dp[start][end], dp[start + 1][end] + min(a[x].del, a[x].add));
44                 dp[start][end] = min(dp[start][end], dp[start][end - 1] + min(a[y].del, a[y].add));
45             }
46         }
47     }
48     cout<<dp[0][m - 1]<<endl;
49 }