C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 612K, 提交时间: 2020-03-09 18:09:35

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;
const ll inf = 1e15;

ll a[30],e[30],c[30][30],dp[60][60],x;
string s,t;
char c1,c2;

void init(){
	for(int i=0;i<26;i++){
		a[i]=e[i]=inf;
		for(int j=0;j<26;j++){
			if(i==j){
				c[i][j]=0;
			}else{
				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++){
			c[i][j]=min(c[i][j],e[i]+a[j]);
			e[i]=min(e[i],c[i][j]+e[j]);
			a[j]=min(a[j],a[i]+c[i][j]);
		}
	} 
}

int main(){
	init();
	cin>>s;
	int n;
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		cin>>t;
		if(t=="add"){
			cin>>c1>>x;
			a[c1-'a']=min(a[c1-'a'],x);
		}else if(t=="erase"){
			cin>>c1>>x;
			e[c1-'a']=min(e[c1-'a'],x);
		}else{
			cin>>c1>>c2>>x;
			c[c1-'a'][c2-'a']=min(c[c1-'a'][c2-'a'],x);
		} 
	}
	Floyd();
	for(int i=2;i<=s.size();i++){
		for(int j=0;j+i-1<s.size();j++){
			int l=j,r=j+i-1;
			dp[l][r]=inf;
			dp[l][r]=min(dp[l][r],min(dp[l+1][r]+e[s[l]-'a'],dp[l][r-1]+e[s[r]-'a']));
			dp[l][r]=min(dp[l][r],dp[l+1][r-1]+e[s[l]-'a']+e[s[r]-'a']);
			for(int k=0;k<26;k++){
				dp[l][r]=min(dp[l][r],dp[l+1][r-1]+c[s[l]-'a'][k]+c[s[r]-'a'][k]);
				dp[l][r]=min(dp[l][r],min(dp[l+1][r]+a[k]+c[s[l]-'a'][k],dp[l][r-1]+a[k]+c[s[r]-'a'][k]));
			}
		}
	}
	cout<<((dp[0][s.size()-1]==inf)?-1:dp[0][s.size()-1])<<endl;
	return 0;
} 

C++(clang++11) 解法, 执行用时: 15ms, 内存消耗: 888K, 提交时间: 2021-01-25 22:35:00

#include<bits/stdc++.h>
using namespace std;
#define LL long long
#define chkmin(x,y) x=min(x,y)
int del[300],add[300],c[300][300];
LL f[55][55];
char s[55];
int m,n;
int main()
{
	cin>>(s+1);
	n=strlen(s+1);
	cin>>m;
	memset(del,0x3f,sizeof(del));
	memset(add,0x3f,sizeof(del));
	memset(c,0x3f,sizeof(c));
	for(int i=1;i<=m;++i)
	{
		char opt[10];
		char c1,c2;
		int cost;
		cin>>(opt+1);
		if(opt[1]=='c')
		{
			cin>>c1>>c2>>cost;
			c[c1-'a'+1][c2-'a'+1]=cost;
		}
		else
		{
			cin>>c1>>cost;
			if(opt[1]=='a')
			add[c1-'a'+1]=cost;
			else 
			del[c1-'a'+1]=cost;
		}
	}
	for(int i=1;i<=26;++i)
	c[i][i]=0;
	for(int k=1;k<=26;++k)
	for(int i=1;i<=26;++i)
	for(int j=1;j<=26;++j)
	c[i][j]=min(c[i][j],c[i][k]+c[k][j]);
	for(int i=1;i<=26;++i)
	for(int j=1;j<=26;++j)
	{
		add[i]=min(add[i],add[j]+c[j][i]);
		del[i]=min(del[i],c[i][j]+del[j]);
	}
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;++i)
	f[i][i]=0,f[i][i-1]=0;
	for(int len=2;len<=n;++len)
	for(int l=1;l<=n-len+1;++l)
	{
		int r=l+len-1;
		int ll=s[l]-'a'+1,rr=s[r]-'a'+1;
		chkmin(f[l][r],f[l][r-1]+del[rr]);
		chkmin(f[l][r],f[l+1][r]+del[ll]);
		for(int k=1;k<=26;++k)
		{
			chkmin(f[l][r],f[l][r-1]+add[k]+c[rr][k]);
			chkmin(f[l][r],f[l+1][r]+add[k]+c[ll][k]);
			chkmin(f[l][r],f[l+1][r-1]+c[ll][k]+c[rr][k]);
		}
	}
	cout<<(f[1][n]>=0x3f3f3f3f?-1:f[1][n]);
	return 0;
}