TopCoder SRM 509 Div1 Medium PalindromizationDiv1

この回は自力では解けず他のコードを参考にした。
http://community.topcoder.com/stat?c=problem_statement&pm=11443

問題

文字列に対し以下のoperationが幾つか与えられる。

• コストxで文字cを任意の位置に追加する
• コストxで文字cを削除する
• コストxで文字c1を1つc2に変換する

文字列wordを回分にするのに必要な最小コストを求めよ。

解法

まずはoperationを整理する。
各文字は直接追加・削除・変換するより、他の文字の変換を経由した方が低コストの場合があるのでWarshall-Floydで最小コストを求めておく。

後は部分文字列に対しメモ付再帰で回文にするコストを最少化する。
メモ付再帰では以下の手順のうち最小値を求める。

• 両端を同じ文字にする
• 片方の端に文字を追加し、両端を同じ文字にする
• 片方の端を削除する

これにより片端または両端の文字を削れるので、より小さな部分文字列について再帰的に処理すればよい。

vector<string> split(const string &str, char delim){
	vector<string> res;
	size_t current = 0, found;
	while((found = str.find_first_of(delim, current)) != string::npos){
		res.push_back(string(str, current, found - current));
		current = found + 1;
	}
	res.push_back(string(str, current, str.size() - current));
	return res;
}

class PalindromizationDiv1 {
	public:
	int N;
	string S;
	ll change[26][26];
	ll add[26];
	ll del[26];
	ll memo[51][51];
	
	ll dodo(int L,int R) {
		if(L>=R) return 0;
		if(memo[L][R]>=0) return memo[L][R];
		memo[L][R]=1LL<<40;
		
		int i;
		FOR(i,26) {
			memo[L][R]=min(memo[L][R],dodo(L+1,R-1)+change[S[L]][i]+change[S[R]][i]);
			memo[L][R]=min(memo[L][R],dodo(L+1,R)+add[i]+change[S[L]][i]);
			memo[L][R]=min(memo[L][R],dodo(L,R-1)+add[i]+change[S[R]][i]);
		}
		memo[L][R]=min(memo[L][R],dodo(L+1,R)+del[S[L]]);
		memo[L][R]=min(memo[L][R],dodo(L,R-1)+del[S[R]]);
		//if(memo[L][R] <1LL<<40) _P("%d %d %lld\n",L,R,memo[L][R]);
		return memo[L][R];
	}
	
	int getMinimumCost(string word, vector <string> operations) {
		int i,x,y,z;
		
		N=operations.size();
		FOR(x,26) FOR(y,26) change[x][y]=1LL<<40;
		FOR(x,26) change[x][x]=0;
		FOR(x,26) add[x]=del[x]=1LL<<40;
		S="";
		FOR(i,word.size()) S+=word[i]-'a';
		
		FOR(i,N) {
			vector<string> OO=split(operations[i],' ');
			if(OO[0]=="erase") del[OO[1][0]-'a']=atoi(OO[2].c_str());
			if(OO[0]=="add") add[OO[1][0]-'a']=atoi(OO[2].c_str());
			if(OO[0]=="change") change[OO[1][0]-'a'][OO[2][0]-'a']=atoi(OO[3].c_str());
		}
		FOR(i,26) FOR(x,26) FOR(y,26) change[x][y]=min(change[x][y],change[x][i]+change[i][y]);
		FOR(y,26) FOR(i,26) FOR(x,26) del[x]=min(del[x],change[x][i]+del[i]);
		FOR(y,26) FOR(i,26) FOR(x,26) add[x]=min(add[x],change[i][x]+add[i]);
		
		MINUS(memo);
		ll res=dodo(0,S.size()-1);
		if(res>=1LL<<40) return -1;
		return (int)res;
	}
};

まとめ

回文問題について、両端をそろえていく再帰・DP法か。覚えておこう。