这个题很多地方暗示了DP的路径。

我们处理时，dp[i][j]可以认为是从i坐标到j坐标的序列达到回文效果需要的最小代价，以此向外扩展，最终得到dp[0][M-1]就是结果。

我们要注意到处理dp[i][j]时，我们需要知道 dp(i+1,j-1)的结果，所以i必须降序，j必须升序，才能保证在计算dp(i,j)时，可以利用已经计算过的结果。

所以 

i应该从M-2 到 0 递减

j在内层 从i+1到M-1 递增

 

在处理dp(i,j)时，第一要看name[i]和name[j]是否相等，如果相等的话，那么直接向内扣一层就可以了

dp[i][j] = dp[i+1][j-1]

否则我们要进行改造，使其成为回文字符串

这个改造有四种方法

1.先让i+1到j是回文的 再在最后加一个name[i]

2.先让i+1到j是回文的 再把前面的name[i]删掉 

3.先让i到j-1是回文的 再在最前面加一个name[j] 

4.先让i到j-1是回文的 再在最后的name[j]删掉 

选择一种消耗最小的方案就可以了。

 

代码如下

#include 
     
      #include 
      
       using namespace std;struct chr{    char c;    int add;    int del;};chr v[30];int N,M;string name;void init(){    cin>>N>>M;    //N是不同字母的数量    //M是原始名字的长度    cin>>name;    //记录字母cost情况    for (int i = 0; i < N; ++i)    {        char c;        cin>>c;        v[c-'a'].c = c;        cin >>v[c-'a'].add >> v[c-'a'].del;    }}unsigned long long dp[2500][2500]={
   0};//存储的是 从第i个字母 到 第j个字母 的回文最小消耗int build(){    //从后向前填满dp[i][j]    for (int i = M-2; i >=0; --i){        for (int j = i + 1 ; j < M; ++j){            if(name[i]==name[j])                dp[i][j] = dp[i+1][j-1];//如果i和j相同 就向内扣一个 不用任何操作            else{                //如果不相同 要考虑四种修改方法                 dp[i][j] = 1<<30;                unsigned long long cs[4];                //注意 此时要保证 i+1,j 和 i,j-1都完成了 所以选择i降序 j升序                cs[0] = dp[i+1][j] + v[name[i]-'a'].add; // 先让i+1到j是回文的 再在最后加一个i                 cs[1] = dp[i+1][j] + v[name[i]-'a'].del; // 先让i+1到j是回文的 再把前面的i删掉                 cs[2] = dp[i][j-1] + v[name[j]-'a'].add; // 先让i到j-1是回文的 再在最前面加一个j                 cs[3] = dp[i][j-1] + v[name[j]-'a'].del; // 先让i到j-1是回文的 再在最后的j删掉                                for(int k = 0; k<4; ++k)                    dp[i][j] = min(dp[i][j],cs[k]);            }        }    }    return dp[0][M-1];}int main(int argc, char const *argv[]){    init();    cout<
       
        <