POJ 3280 Cheapest Palindrome（回文串， 区间DP）

回文串
题目意思：
给出一个字符串，然后给出n个字符，删除该字符和插入该字符的花费。
问：删除或插入若干字符，使得该字符串变为回文串，所需要的代价花费最少。
注意到，删除某个字符和插入某个字符是等价的，用数组 w 存放某个字符 删除后插入的较小值即可。
本题要点：
1、状态表示：
dp[i][j] 表示s的子区间 [i, j] 变为回文串的最小花费
2、转态转移：
dp[i][j] = dp[i + 1][j - 1], s[i] == s[j]
dp[i][j] = min(dp[i + 1][j] + w[s[i] - ‘a’], dp[i][j - 1] + w[s[j] - ‘a’]), s[i] != s[j]

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int MaxN = 2010;
int w[30], n, m, dp[MaxN][MaxN];	//dp[i][j] 表示s的子区间 [i, j] 变为回文串的最小花费
char s[MaxN], ch[2];void sovle()
{
    memset(dp, 0, sizeof dp);for(int i = m - 1; i >= 0; --i){
    for(int j = i + 1; j < m; ++j)	//i是起点，j是区间终点{
    if(s[i] == s[j])	{
    if(j - i > 1){
    dp[i][j] = dp[i + 1][j - 1];}}else{
    dp[i][j] = min(dp[i + 1][j] + w[s[i] - 'a'], dp[i][j - 1] + w[s[j] - 'a']);	}}}printf("%d\n", dp[0][m - 1]);
}int main()
{
    int x, y;while(scanf("%d%d", &n, &m) != EOF){
    scanf("%s", s);for(int i = 0; i < n; ++i){
    scanf("%s%d%d", ch, &x, &y);w[ch[0] - 'a'] = min(x, y);}sovle();}return 0;
}/* 3 4 abcb a 1000 1100 b 350 700 c 200 800 *//* 900 */