牛牛的回文串（区间dp）

题目描述

牛牛喜欢回文串，牛妹给了牛牛一个字符串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部分后都是不同的

输出描述:

输出一个整数

示例1

输入

racecar
0

输出

0

示例2

输入

caaaaaab
change b a 100000
change c a 100000
change c d 50000
change b e 50000
erase d 50000
erase e 49999

输出

199999

示例3

输入

moon
erase o 5
add u 7
change d p 3
change m s 12
change n d 6
change s l 1

输出

-1

示例4

输入

xab
change a c 1
change b d 1
change c e 1
change d e 1
add y 1
change y z 1
change x z 1

输出

7

AC代码：

#include<stdio.h>
#include<iostream>
#include<string.h>
#define INF 1e14 
#define LL long long
using namespace std;
char str[55];
LL dp[55][55],cost_add[30],cost[30],cost_err[30],C[30][30];//变换表 
//dp[i][j]代表i~j段对称的最小花费   
void init(){//初始化 
     for(int i=0;i<=26;i++){
        cost[i]=cost_add[i]=cost_err[i]=INF;
        for(int j=0;j<=26;j++)
         C[i][j]=INF;
    }   
}
void Floyd(){
   for(int k=0;k<26;k++)
     for(int i=0;i<26;i++)
      for(int j=0;j<26;j++)
        C[i][j]=min(C[i][j],C[i][k]+C[k][j]);//建立变换表 
    for(int i=0;i<26;i++)
     for(int j=0;j<26;j++)
    {
        cost[i]=min(cost[i],min(cost_add[i],cost_err[i]));//直接通过增加或则删除该字母 
        cost[i]=min(cost[i],C[i][j]+min(cost_err[j],cost_add[j]));//间接接通过先变换再增加或则删除该字母
        cost[i]=min(cost[i],cost_add[j]+C[j][i]);//增加该字母再改变到需要的字母 
        for(int k=0;k<26;k++)
          cost[i]=min(cost[i],C[i][j]+cost_add[k]+C[k][j]);//一边增加 一边变换中间字母 
    }
}
int main()
{
   scanf("%s",str+1);
    int m,x;
    char in[10];
    char a,b;
    scanf("%d",&m);
    init(); 
    for(int i=0;i<m;i++){
        scanf("%s",in);getchar();
        if(in[0]=='a')scanf("%c %d",&a,&x),cost_add[a-'a']=min(cost_add[a-'a'],(LL)x);
        if(in[0]=='e')scanf("%c %d",&a,&x),cost_err[a-'a']=min(cost_err[a-'a'],(LL)x);
        if(in[0]=='c')scanf("%c %c %d",&a,&b,&x),C[a-'a'][b-'a']=min(C[a-'a'][b-'a'],(LL)x);

<span class="token punctuation">}</span>
<span class="token function">Floyd</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment" spellcheck="true">//&#x5F17;&#x6D1B;&#x4F0A;&#x5FB7;&#x5EFA;&#x7ACB;&#x82B1;&#x8D39;&#x8868; </span>
<span class="token keyword">int</span> len<span class="token operator">=</span><span class="token function">strlen</span><span class="token punctuation">(</span>str<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token operator">=</span>len<span class="token punctuation">;</span>i<span class="token operator">&gt;=</span><span class="token number">1</span><span class="token punctuation">;</span>i<span class="token operator">--</span><span class="token punctuation">)</span>
 <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">;</span>j<span class="token operator">&lt;=</span>len<span class="token punctuation">;</span>j<span class="token operator">++</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
    dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span>INF<span class="token punctuation">;</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>str<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">==</span>str<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span>dp<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token number">-1</span><span class="token punctuation">]</span><span class="token punctuation">;</span><span class="token comment" spellcheck="true">//&#x76F8;&#x540C;&#x5219;&#x4E0D;&#x82B1;&#x8D39; </span>
    dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">min</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span>dp<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">+</span>cost<span class="token punctuation">[</span>str<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-</span><span class="token string">&apos;a&apos;</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment" spellcheck="true">//&#x5904;&#x7406;&#x5DE6;&#x8FB9; </span>
    dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">min</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token number">-1</span><span class="token punctuation">]</span><span class="token operator">+</span>cost<span class="token punctuation">[</span>str<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">-</span><span class="token string">&apos;a&apos;</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment" spellcheck="true">//&#x5904;&#x7406;&#x53F3;&#x8FB9; </span>
    dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">min</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span>dp<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token number">-1</span><span class="token punctuation">]</span><span class="token operator">+</span><span class="token function">min</span><span class="token punctuation">(</span>C<span class="token punctuation">[</span>str<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">-</span><span class="token string">&apos;a&apos;</span><span class="token punctuation">]</span><span class="token punctuation">[</span>str<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-</span><span class="token string">&apos;a&apos;</span><span class="token punctuation">]</span><span class="token punctuation">,</span>C<span class="token punctuation">[</span>str<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-</span><span class="token string">&apos;a&apos;</span><span class="token punctuation">]</span><span class="token punctuation">[</span>str<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">-</span><span class="token string">&apos;a&apos;</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span><span class="token comment" spellcheck="true">//&#x4E24;&#x8FB9;&#x540C;&#x65F6;&#x53D8;&#x6362;&#x4E2D;&#x5B57;&#x6BCD; </span>
    <span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> k<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span>k<span class="token operator">&lt;=</span><span class="token number">26</span><span class="token punctuation">;</span>k<span class="token operator">++</span><span class="token punctuation">)</span>
        dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">=</span><span class="token function">min</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span>dp<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>j<span class="token number">-1</span><span class="token punctuation">]</span><span class="token operator">+</span>C<span class="token punctuation">[</span>str<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token operator">-</span><span class="token string">&apos;a&apos;</span><span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token operator">+</span>C<span class="token punctuation">[</span>str<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token operator">-</span><span class="token string">&apos;a&apos;</span><span class="token punctuation">]</span><span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>dp<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>len<span class="token punctuation">]</span><span class="token operator">==</span>INF<span class="token punctuation">)</span> cout<span class="token operator">&lt;&lt;</span><span class="token string">&quot;-1&quot;</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span><span class="token keyword">else</span> cout<span class="token operator">&lt;&lt;</span>dp<span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">[</span>len<span class="token punctuation">]</span><span class="token operator">&lt;&lt;</span>endl<span class="token punctuation">;</span>
<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
}