题目链接：

题目大意：给定一个字符串，可以删除增加，每个操作都有代价，求出将字符串转换成回文串的最小代价

Sample Input

3 4abcba 1000 1100b 350 700c 200 800

Sample Output

900

分析：这是一道最长回文串的变形，就是LCS

　　一串字符要变成回文，对于一个字符来说，删掉它，或者增加对称的一个该字符，都能达到回文的效果，所以是等价的。所以取代价的的时候选择最小的就可以。

　　至于动态规划方程：令dp[i][j]表示从第 i 个字符到第j个字符变成回文的最小代价，初始为0。接着LCS

dp[i][j] = min(dp[i+1][j]+cost[s[i]-'a'] , dp[i][j-1]+cost[s[j]-'a']) ;                 if(s[i]==s[j])　　dp[i][j] = min(dp[i+1][j-1],dp[i][j]);

代码如下：

1 # include
     
       2 # include
      
        3 # define maxn 2005 4 char s[maxn]; 5 int dp[maxn][maxn],cost[maxn]; 6  7 int min(int a,int b){ 8     return a
       =1;i--){26                 dp[i][j] = min(dp[i+1][j]+cost[s[i]-'a'] , dp[i][j-1]+cost[s[j]-'a']) ;27                 if(s[i]==s[j])28                     dp[i][j] = min(dp[i+1][j-1],dp[i][j]);29             }30         }31         printf("%d\n",dp[1][m]);32     }33     return 0;34 }