牛客dp虽然对于入门学dp的...很不开心,但是感觉题目还是很好的...
这题大概利用了Floyd和最长公共子序列的思想吧..
题目描述:

牛牛喜欢回文串，牛妹给了牛牛一个字符串S，牛牛想把S变成回文串
牛牛可以做如下三种操作
1：在任意位置增加一个字符
2：删除一个字符
3：改变一个字符
每种操作都有限定的字符，比如，只能删除'a',增加'b',把'c'变成'd'等等
每种操作都有相应的代价
用M条语句来描述能进行的操作
add c x 表示增加c字符需要x的代价
erase c x表示删除c字符需要x的代价
change c1 c2 x表示将c1 改成c2需要x的代价
求牛牛想要得到回文串需要的最少代价
如果不行输出-1
输入描述:
第一行输入一个字符串S(都是小写字母)表示牛妹给牛牛的串(1 ≤ |S| ≤ 50)
第二行输入一个整数m (0 ≤ m ≤ 50)
接下来m行的格式是
add c x
erase c x
change c1 c2 x
三种中的一种
c c1 c2都是小写字母
1 ≤ x ≤ 100000
所有允许的操作去除x部分后都是不同的

思路,大概就是考虑每个地方转化成回文串的最小价值直接dp即可.
ac代码如下:

#include <bits/stdc++.h>
using namespace std;
#define int long long 
const int inf=1e16;
const int N=55,M=30;
int dp[N][N];//i~j段转化为回文串的最小代价.
char s[N];
int cost_a[M],cost_e[M],cost_c[M][M],cost[M];
//分别表示增加/删除/改变的最小花费,以及处理该字符的最小花费.
void init()
{
    //处理出来cost_c数组的最小转化.
    for(int k=0;k<26;k++)
    {
        for(int i=0;i<26;i++)
        {
            for(int j=0;j<26;j++)
            {
                cost_c[i][j]=min(cost_c[i][j],cost_c[i][k]+cost_c[k][j]);
            }
        }
    }
    //处理出处理某个字母的最小的代价cost.
    for(int i=0;i<26;i++)
    {
        cost[i]=min(cost_a[i],cost_e[i]);//直接通过增加/删除得到代价.
        for(int j=0;j<26;j++)
        {
            //把i转化为j再增加/把i转化为j再删除.
            cost[i]=min(cost[i],cost_c[i][j]+min(cost_a[j],cost_e[j]));
            //增加一个j转化成i
            cost[i]=min(cost[i],cost_c[j][i]+cost_a[j]);
            for(int k=0;k<26;k++)
            {
                //把i转化成k且增加一个j把j转化成k
                cost[i]=min(cost[i],cost_c[i][k]+cost_a[j]+cost_c[j][k]);
            }
        }
    }
}

signed main()
{
    for(int i=0;i<26;i++)
    {
        cost_a[i]=cost_e[i]=cost[i]=inf;
        for(int j=0;j<26;j++)
        {
            cost_c[i][j]=inf;
        }
    }
    scanf("%s",s+1);
    int T;
    scanf("%lld",&T);
    while(T--)
    {
        char a[10];
        scanf("%s",a);
        if(a[0]=='a')
        {
            char c[2];int x;
            scanf("%s%lld",c,&x);
            cost_a[c[0]-'a']=min(cost_a[c[0]-'a'],x);
        }
        else if(a[0]=='e')
        {
            char c[2];int x;
            scanf("%s%lld",c,&x);
            cost_e[c[0]-'a']=min(cost_e[c[0]-'a'],x);
        }
        else
        {
            char c1[2],c2[2];int x;
            scanf("%s%s%lld",c1,c2,&x);
            cost_c[c1[0]-'a'][c2[0]-'a']=min(cost_c[c1[0]-'a'][c2[0]-'a'],x);
        }
    }
    init();
    /*
    直接dp
    dp[i+1~len][j-1~len]是已知的.我们需要根据已知更新未知
    */
    int len=strlen(s+1);
    for(int i=len;i>=1;i--)
    {
        for(int j=i+1;j<=len;j++)
        {
            dp[i][j]=inf;
            if(s[i]==s[j]) dp[i][j]=dp[i+1][j-1];
            dp[i][j]=min(dp[i][j],dp[i+1][j]+cost[s[i]-'a']);
            dp[i][j]=min(dp[i][j],dp[i][j-1]+cost[s[j]-'a']);
            dp[i][j]=min(dp[i][j],dp[i+1][j-1]+min(cost_c[s[i]-'a'][s[j]-'a'],cost_c[s[j]-'a'][s[i]-'a']));
            for(int k=0;k<26;k++)
            {
                dp[i][j]=min(dp[i][j],dp[i+1][j-1]+cost_c[s[i]-'a'][k]+cost_c[s[j]-'a'][k]);
            }
        }
    }
    if(dp[1][len]==inf) puts("-1");
    else printf("%lld\n",dp[1][len]);
    return 0;
}

友情提示,可能因为变化过多而爆你的inf,所以...emm不用我说了吧= - =