题目链接
牛牛喜欢回文串，牛妹给了牛牛一个字符串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 串的长度<=50
用dp(i,j)表示把[i, j]这一区间变成回文串的最小代价，那么dp(i, j)可以由dp(i+1, j), dp(i, j-1), dp(i+1, j-1)这三种状态转移而来。 但是因为它给出的操作可以出现很多变换，直接进行它所给的操作有可能不会得到最优解：比如change(a,c) = 10,add( a ) = 1,add( c ) = 100,那么直接add( c )的代价要比先add( a )再change(a,c)要大，而change之间也类似。所以我们用类似最短路的算法预处理出所有类型操作的最小费用(代价为inf = 不能进行该操作)。 预处理完之后，对于区间(i, j)，它可能的转移：
擦除其中一个端点的代价 + 剩余部分为回文的代价擦除两个端点的代价 + 剩余部分为回文的代价在其中一边添加字符v，并让另一边的端点变为字符v 的代价 + 去除两端点剩余部分为回文的代价（枚举字符v）把两个端点都变成字符v的代价 + 剩余部分为回文的代价。AC代码：
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 55; const ll inf = 0x3f3f3f3f; ll dp[maxn][maxn]; char s[maxn]; int a[maxn]; ll add[maxn],era[maxn],to[maxn][maxn]; void up_add(){//spfa思想更新add操作 int inq[30]; queue<int> q; for(int i = 0; i < 26; ++i){ q.push(i);inq[i] = 1; } while(q.size()){ int u = q.front();q.pop();inq[u] = 0; for(int i = 0;i < 26;++i){ if(add[i] > add[u] + to[u][i]){ add[i] = add[u] + to[u][i]; if(!inq[i]) q.push(i), inq[i] = 1; } } } } void up_era(){//spfa思想更新era操作 int inq[30]; queue<int> q; for(int i = 0; i < 26; ++i){ q.push(i);inq[i] = 1; } while(q.size()){ int u = q.front();q.pop();inq[u] = 0; for(int i = 0;i < 26;++i){ if(era[i] > to[i][u] + era[u]){ era[i] = to[i][u] + era[u]; if(!inq[i]) q.push(i), inq[i] = 1; } } } } ll cul(int l,int r){ if(l > r) return 0; return dp[l][r]; } int main(){ // memset(dp,0x3f,sizeof dp); // memset(add,0x3f,sizeof add); // memset(era,0x3f,sizeof era); // memset(to,0x3f,sizeof to); for(int i = 0; i < maxn; ++i){//因为后面可能会出现3个inf相加， //所以inf定小一点防止爆ll add[i] = era[i] = inf; for(int j = 0; j < maxn; ++j){ dp[i][j] = to[i][j] = inf; } } scanf("%s",s+1); int len = strlen(s+1); for(int i = 1; i <= len; ++i) a[i] = s[i] - 'a'; for(int i = 1; i <= len; ++i) dp[i][i] = 0; int n; scanf("%d",&n); while(n--){ char op[10],c[2]; int x; scanf("%s",op); if(op[0] == 'a'){ scanf("%s%d",c,&x); add[c[0]-'a'] = x; } else if(op[0] == 'e'){ scanf("%s%d",c,&x); era[c[0]-'a'] = x; } else{ char c2[2]; scanf("%s%s%d",c,c2,&x); to[c[0]-'a'][c2[0]-'a'] = x; } } for(int k = 0; k < 26; ++k) {//Floyd思想更新to操作 for(int i = 0; i < 26; ++i){ for(int j = 0; j < 26; ++j){ if(i == j) to[i][j] = 0; to[i][j] = min(to[i][j],to[i][k] + to[k][j]); } } } up_add(); up_era(); for(int d = 1; d < len; ++d){ for(int r = d+1; r <= len; ++r){ int l = r - d; //erase dp[l][r] = min(cul(l+1, r) + era[a[l]], dp[l][r]); dp[l][r] = min(cul(l, r-1) + era[a[r]], dp[l][r]); dp[l][r] = min(cul(l+1, r-1) + era[a[l]] + era[a[r]], dp[l][r]); //add && change for(int v = 0; v < 26; ++v){ dp[l][r] = min(dp[l][r], cul(l, r-1) + add[v] + to[a[r]][v]); dp[l][r] = min(dp[l][r], cul(l+1, r) + add[v] + to[a[l]][v]); dp[l][r] = min(dp[l][r], cul(l+1, r-1) + to[a[r]][v] + to[a[l]][v]); } //cout<<"l:"<<l<<" r:"<<r<<" dp[l][r]:"<<dp[l][r]<<endl; } } ll ans = dp[1][len]; if(ans == inf) printf("-1\n"); else printf("%lld\n",ans); }