POJ3280 Cheapest Palindrome 区间DP

　　典型的区间DP问题，fp[i][j]表示第i-j个字符经过修改后的最优值，则状态转移方程如下：

                f[i][j]=Min(f[i][j],f[i][j-1]+Min(cost[s[j]][0],cost[s[j]][1]));
                f[i][j]=Min(f[i][j],f[i+1][j]+Min(cost[s[i]][0],cost[s[i]][1]));
                if(s[i]==s[j]) f[i][j]=Min(f[i][j],f[i+1][j-1]);

 1 //STATUS:C++_AC_94MS_14008KB
 2 #include<stdio.h>
 3 #include<stdlib.h>
 4 #include<string.h>
 5 #include<math.h>
 6 #include<iostream>
 7 #include<string>
 8 #include<algorithm>
 9 #include<vector>
10 #include<queue>
11 #include<stack>
12 using namespace std;
13 #define LL __int64
14 #define pii pair<int,int>
15 #define Max(a,b) ((a)>(b)?(a):(b))
16 #define Min(a,b) ((a)<(b)?(a):(b))
17 #define mem(a,b) memset(a,b,sizeof(a))
18 #define lson l,mid,rt<<1
19 #define rson mid+1,r,rt<<1|1
20 const int N=2010,INF=0x3f3f3f3f,MOD=100000000;
21 const double DNF=100000000000;
22 
23 char s[N];
24 int f[N][N],cost[130][2];
25 int n,m;
26 
27 int main()
28 {
29  //   freopen("in.txt","r",stdin);
30     int i,j,a,b,k;
31     char op[2];
32     while(~scanf("%d%d",&n,&m))
33     {
34         scanf("%s",s);
35         for(i=0;i<n;i++){
36             scanf("%s%d%d",op,&a,&b);
37             cost[op[0]][0]=a;
38             cost[op[0]][1]=b;
39         }
40         for(k=1;k<m;k++){
41             for(i=0;i+k<m;i++){
42                 j=i+k;
43                 f[i][j]=INF;
44                 f[i][j]=Min(f[i][j],f[i][j-1]+Min(cost[s[j]][0],cost[s[j]][1]));
45                 f[i][j]=Min(f[i][j],f[i+1][j]+Min(cost[s[i]][0],cost[s[i]][1]));
46                 if(s[i]==s[j])
47                     f[i][j]=Min(f[i][j],f[i+1][j-1]);
48             }
49         }
50         printf("%d\n",f[0][m-1]);
51     }
52     return 0;
53 }