poj3280 cheapest palindrome

题目链接：https://vjudge.net/problem/POJ-3280

区间dp。设dp[i][j]表示从原串c的位置i到位置j,变成回文所需要的最小代价。

有如下情况：

1) c[i]=c[j]，则dp[i][j]=dp[i+1][j-1]

2) c[i]≠c[j]，对于左边的c[i]，可以删除c[i]或者在j的右边添加c[i]，对于右边的c[j]同理

则dp[i][j]=min(dp[i][j-1]+t1[c[j]-'a+1],dp[i][j-1]+t2[c[j]-'a'+1],dp[i+1][j]+t1[c[i]-'a'+1],dp[i+1][j]+t2[c[i]-'a'+1])

此处数组t1表示插入字符的代价，t2表示删除字符的代价

 1 #include<iostream>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<cstdio>
 5 using namespace std;
 6 const int maxm=20+10;
 7 const int inf=0x3f3f3f;
 8 char c[maxm];
 9 int t1[30],t2[30];
10 int dp[maxm][maxm];
11 int main(){
12     int i,j,n,m,x,y,min1,min2,k;
13     char ch;
14     freopen("poj3280.txt","r",stdin);
15     cin>>n>>m;getchar(); //*
16     for (i=1;i<=m;i++) cin>>c[i];
17     getchar(); //*
18     for (i=1;i<=n;i++){
19           cin>>ch>>x>>y;
20           t1[ch-'a'+1]=x;t2[ch-'a'+1]=y;
21       }
22     memset(dp,0,sizeof(dp));
23     for (k=1;k<=m-1;k++)
24       for (i=1;i<=m;i++)
25         if (i+k<=m){
26               j=i+k;
27               dp[i][j]=inf;
28         if (c[i]==c[j]) dp[i][j]=min(dp[i][j],dp[i+1][j-1]);
29               min1=dp[i+1][j]+min(t1[c[i]-'a'+1],t2[c[i]-'a'+1]);dp[i][j]=min(dp[i][j],min1);
30               min2=dp[i][j-1]+min(t1[c[j]-'a'+1],t2[c[j]-'a'+1]);dp[i][j]=min(dp[i][j],min2);
31          }
32     cout<<dp[1][m]<<endl;
33     fclose(stdin);
34     return 0;
35 }

poj3280