yukicoder : No.422 文字列変更 (Hard)

今回珍しくWA無しだったな。
http://yukicoder.me/problems/no/422

問題

２つの文字列S,Tがある。
Sに以下の処理を繰り返し、Tにしたい。

• S中の１文字を任意の文字に置換する。コストが5かかる。
• S中の連続する部分文字列を削除する。N文字削除するのにコストが(9+2(N-1))かかる。
• S中に文字列を追加する。N文字追加するのにコストが(9+2(N-1))かかる。

総コストの最小値を求めよ。
また、SをTにするときの追加・削除した位置を出力せよ。

解法

LCSにひと工夫加える。
以下の状態に対しDPで最小コストを求める。
dp(s,t,type) := Sの先頭s文字までとTの先頭t文字までを一致させ、かつS[s]をT[t]と一致させるのに取った処理typeが置換・削除・追加である時の最小コスト
あとはDPの結果をバックトラックして答えよう。

なお、自分は最初Tも加工できると勘違いしたが、それでもAC取れてしまった…。

int N,M;
string S,T;
int dp[1300][1300][3];
int pat[1300][1300][3];

string RS,RT;

int dpdp(int s,int t,int st) { // 0-none 1-add 2-del
	if(s==N && t==M) return 0;
	int& ret=dp[s][t][st];
	if(ret>=0) return ret;
	
	ret=10101010;
	//match
	if(s<N && t<M) ret = min(ret, dpdp(s+1,t+1,0)+((S[s]==T[t])?0:5));
	// del
	if(s<N) ret = min(ret, dpdp(s+1,t,2)+((st==2)?2:9));
	// add
	if(t<M) ret = min(ret, dpdp(s,t+1,1)+((st==1)?2:9));
	return ret;
}

void dfs(int s,int t,int st) {
	if(s==N && t==M) return;
	int& ret=dp[s][t][st];
	
	if(s<N && t<M && ret==dpdp(s+1,t+1,0)+((S[s]==T[t])?0:5)) RS+=S[s], RT+=T[t], dfs(s+1,t+1,0);
	else if(s<N && ret==dpdp(s+1,t,2)+((st==2)?2:9))       RS+=S[s], RT+='-',  dfs(s+1,t,2);
	else RS+='-', RT+=T[t], dfs(s,t+1,1);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M>>S>>T;
	MINUS(dp);
	
	cout<<dpdp(0,0,0)<<endl;
	dfs(0,0,0);
	cout<<RS<<endl<<RT<<endl;
	
}

まとめ

Writer解説を理解していない…。