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; } };