牛牛的回文串（区间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
6
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
6
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
7
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);
     
    
   

    

     

    
    

     
         
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    Floyd();//弗洛伊德建立花费表 
     
    
   

    

     

    
    

     
    int len=strlen(str+1);
     
    
   

    

     

    
    

     
    for(int i=len;i>=1;i--)
     
    
   

    

     

    
    

     
     for(int j=i+1;j<=len;j++)
     
    
   

    

     

    
    

     

          {
     
    
   

    

     

    
    

     

              dp[i][j]=INF;
     
    
   

    

     

    
    

     
        if(str[i]==str[j]) dp[i][j]=dp[i+1][j-1];//相同则不花费 
     
    
   

    

     

    
    

     

              dp[i][j]=min(dp[i][j],dp[i+1][j]+cost[str[i]-'a']);//处理左边 
     
    
   

    

     

    
    

     

              dp[i][j]=min(dp[i][j],dp[i][j-1]+cost[str[j]-'a']);//处理右边 
     
    
   

    

     

    
    

     

              dp[i][j]=min(dp[i][j],dp[i+1][j-1]+min(C[str[j]-'a'][str[i]-'a'],C[str[i]-'a'][str[j]-'a']));//两边同时变换中字母 
     
    
   

    

     

    
    

     
        for(int k=0;k<=26;k++)
     
    
   

    

     

    
    

     

                  dp[i][j]=min(dp[i][j],dp[i+1][j-1]+C[str[i]-'a'][k]+C[str[j]-'a'][k]);
     
    
   

    

     

    
    

     

          }
     
    
   

    

     

    
    

     
    if(dp[1][len]==INF) cout<<"-1"<<endl;else cout<<dp[1][len]<<endl;
     
    
   

    

     

    
    

     
    return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

  
 
 

文章来源: fivecc.blog.csdn.net，作者：Five-菜鸟级，版权归原作者所有，如需转载，请联系作者。

原文链接：fivecc.blog.csdn.net/article/details/90488147