POJ 3280 Cheapest Palindrome（区间DP求改成回文串的最小花费）

题目链接：http://poj.org/problem?id=3280

题目大意：给你一个字符串，你可以删除或者增加任意字符，对应有相应的花费，让你通过这些操作使得字符串变为回文串，求最小花费。
解题思路：
比较简单的区间DP,令dp[i][j]表示使[i,j]回文的最小花费。
则得到状态转移方程：
dp[i][j]=min(dp[i][j],min(add[str[i]-'a'],del[str[i]-'a'])+dp[i+1][j]);
dp[i][j]=min(dp[i][j],min(add[str[j]-'a'],del[str[j]-'a'])+dp[i][j-1]);
if(str[i]==str[j])
dp[i][j]=min(dp[i][j],dp[i+1][j-1]);

代码：

 #include<cstdio>

 #include<cmath>

 #include<cctype>

 #include<cstring>

 #include<iostream>

 #include<algorithm>

 #include<vector>

 #include<queue>

 #include<set>

 #include<map>

 #include<stack>

 #include<string>

 #define lc(a) (a<<1)

 #define rc(a) (a<<1|1)

 #define MID(a,b) ((a+b)>>1)

 #define fin(name)  freopen(name,"r",stdin)

 #define fout(name) freopen(name,"w",stdout)

 #define clr(arr,val) memset(arr,val,sizeof(arr))

 #define _for(i,start,end) for(int i=start;i<=end;i++)

 #define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

 using namespace std;

 typedef long long LL;

 const int N=3e3+;

 const int INF=0x3f3f3f3f;

 const double eps=1e-;

 int add[],del[];

 int dp[N][N];

 char str[N];

 int main(){

     FAST_IO;

     int n,m;

     while(cin>>n>>m){

         memset(dp,,sizeof(dp));

         cin>>str;

         for(int i=;i<=n;i++){

             char ch;

             int v1,v2;

             cin>>ch>>v1>>v2;

             add[ch-'a']=v1;

             del[ch-'a']=v2;

         }

         for(int len=;len<m;len++){

             for(int i=;i+len<m;i++){

                 int j=len+i;

                 dp[i][j]=INF;

                 dp[i][j]=min(dp[i][j],min(add[str[i]-'a'],del[str[i]-'a'])+dp[i+][j]);

                 dp[i][j]=min(dp[i][j],min(add[str[j]-'a'],del[str[j]-'a'])+dp[i][j-]);

                 if(str[i]==str[j]){

                     dp[i][j]=min(dp[i][j],dp[i+][j-]);

                 }

             }

         }

         printf("%d\n",dp[][m-]);

     }

     return ;

 }