题目链接
http://poj.org/problem?id=3280
? 题意为给定一个字符串，该字符串包含n种字符，长度为m。给定每种字符的增添和删除所需的消耗，问如何消耗最少让原串变为回文串。
? 则是区间dp的明显形式，最终的从头至尾可以由字串增添或删减得到。可以分为三种情况讨论。
??1.s[i] == s[j]易得dp[i][j] = dp[i + 1][j - 1];
??2.s[i] != s[j]设i + 1到j已经为回文，则在尾部增加i所对应的字符或是删去i；
??3.s[i] != s[j]设j - 1到i已经为回文，则在则在尾部增加j所对应的字符或是删去j；
?取上述三种的最小值便是所求值。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <map>
#define rep(i, s, t) for(int i = s;i <= t;i++)
#define rap(i, s, t) for(int i = s;i >= t;i--)
#define inf 0x3f3f3f3f
using namespace std;
int dcost[30], icost[30];
map<int, int>M;
int n, m;
char stand[2004];
int dp[2004][2004];
int main()
{while(scanf("%d%d", &n, &m) != EOF){M.clear();scanf("%s", stand);int len = strlen(stand);int cnt = 0;rep(i, 0, len - 1){if(M[stand[i] - 'a'] == 0){M[stand[i] - 'a'] = ++cnt;}}rep(i, 1, n){char ls[2];scanf("%s", ls);scanf("%d%d", &icost[M[ls[0] - 'a']], &dcost[M[ls[0] - 'a']]);}
// map<int,int>::iterator it;
// for(it = M.begin();it != M.end();it++)
// {
// printf("%c %d %d %d\n", it->first + 'a', it->second, icost[it->second], dcost[it->second]);
// }memset(dp, 0, sizeof(dp));
// rep(i, 0, len - 1)
// dp[i][i] = 0;rep(l, 2, len){rep(i, 0, len - l){int j = l + i - 1;dp[i][j] = min(min(dp[i + 1][j] + dcost[M[stand[i] - 'a']], dp[i + 1][j] + icost[M[stand[i] - 'a']]),min(dp[i][j - 1] + dcost[M[stand[j] - 'a']], dp[i][j - 1] + icost[M[stand[j] - 'a']]));if(stand[i] == stand[j])dp[i][j] = min(dp[i][j], dp[i + 1][j - 1]);}}printf("%d\n", dp[0][len - 1]);}return 0;
}