牛牛的回文串(区间dp)
登录—专业IT笔试面试备考平台_牛客网
https://ac.nowcoder.com/acm/problem/21337
题目描述牛牛喜欢回文串,牛妹给了牛牛一个字符串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 xerase c xchange c1 c2 x三种中的一种c c1 c2都是小写字母1 ≤ x ≤ 100000所有允许的操作去除x部分后都是不同的输出描述:输出一个整数示例1
输入racecar0输出0示例2
输入caaaaaab6change b a 100000change c a 100000change c d 50000change b e 50000erase d 50000erase e 49999输出199999示例3
输入moon6erase o 5add u 7change d p 3change m s 12change n d 6change s l 1输出-1示例4
输入xab7change a c 1change b d 1change c e 1change d e 1add y 1change y z 1change 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;
}
ACM 算法 文章被收录于专栏
分享一点经验和拙见