SRM 509 Div1 Medium PalindromizationDiv1

問題概要

文字列が与えられる。これを、与えられた操作を用いて回文にする、最小のコストを求めよ。


操作は、
add x c(xを文字列の任意の場所に挿入する。コストc)
erase x c(xを文字列から削除する。コストc)
change a b c(文字列中のaを一つ選びそれをbに変更する。コストc)

がいくつか並べられて与えられる。

制約条件

文字列の長さ≦50

方針

文字の変更、削除、挿入は前準備でテーブルにしておく。
変更はワーシャルフロイドをしてA→B→Cのような変更ができるように対応する。


dp部分は編集距離的なDPである。
dp[s][t]にs文字目からt文字目までを回文にするコストをもたせてメモ化再帰


適用できる操作は、

  • s,tの文字を別の文字(26通り)に変更
  • sの文字を別の文字に変えて削除
  • tの文字を別の文字に変えて削除
  • sに回文として対応する文字を挿入して、sをその文字に変更
  • tに回文として対応する文字を挿入して、sをその文字に変更

ソースコード

int w[50],l;
int cn[26][26], del[26], ins[26];
int dp[50][50];

int rec(int s,int t){
	if(s>=t)return 0;
	int &ret=dp[s][t];
	if(ret>=0)return ret;
	ret=inf;
	
	//cerr<<s<<" "<<t<<endl;
	
	ret=min(ret,rec(s+1,t)+del[w[s]]);
	ret=min(ret,rec(s,t-1)+del[w[t]]);
	rep(i,26){
		ret=min(ret,rec(s+1,t)+ins[i]+cn[w[s]][i]);
		ret=min(ret,rec(s,t-1)+ins[i]+cn[w[t]][i]);
		ret=min(ret,rec(s+1,t-1)+cn[w[s]][i]+cn[w[t]][i]);
	}
	return ret;
}

class PalindromizationDiv1 {
	public:
	int getMinimumCost(string word, vector <string> operations) 
	{
		l=word.size();
		rep(i,l)w[i]=word[i]-'a';
		rep(i,26)rep(j,26)cn[i][j]=inf;
		rep(i,26)del[i]=ins[i]=inf, cn[i][i]=0;
		
		fr(i,operations){
			string s; char a,b; int c;
			stringstream ss(*i);
			
			ss>>s;
			if(s=="add")ss>>a>>c, ins[a-'a']=c;
			if(s=="erase")ss>>a>>c, del[a-'a']=c;
			if(s=="change")ss>>a>>b>>c, cn[a-'a'][b-'a']=c;
		}
		
		rep(k,26)rep(i,26)rep(j,26)cn[i][j]=min(cn[i][j], cn[i][k]+cn[k][j]);
		rep(i,26)rep(j,26)ins[i]=min(ins[i],ins[j]+cn[j][i]);
		rep(i,26)rep(j,26)del[i]=min(del[i],del[j]+cn[i][j]);
		
		rep(i,50)rep(j,50)dp[i][j]=-1;
		int ans=rec(0,l-1);
		return ans==inf?-1:ans;
	}
};