TopCoder SRM 566 Div2 Medium PenguinPals

続いてDiv2 Medium。
http://community.topcoder.com/stat?c=problem_statement&pm=12355

円形に赤か青のペンギンが並んでいる。同じ色のペンギンをペアにしたとき、ペアのペンギン同士を結ぶ線分が交差しないようにして出来るペア数の最大値を求める。

円周の始点・終点を指定してできる弓型内のペア数を再帰的に考えていく。
弓型の最初の点を使わない場合、残りの点からなる弓型のペア数がその弓型のペア数になる。
弓型の最初の点を使う場合、ペア候補の点を１個選んでペアを作ると、その最初の点とペア候補の点からなる線により、点が２つの弓側に分かれるので再帰的に処理できる。

メモ化再帰の状態数は探索する円の始点・終点の２つだけなので、O(N^2)で終わる。

class PenguinPals {
	string C;
	int memo[100][100];
	public:
	int val(int x,int y) {
		if(x>=y) return 0;
		int& res = memo[x][y];
		if(res!=-1) return res;
		
		//使わない
		res = val(x+1,y);
		
		int i;
		for(i=x+1;i<=y;i++) if(C[x]==C[i]) res = max(res, 1+ val(x+1,i-1) + val(i+1,y));
		return res;
	}
	
	int findMaximumMatching(string colors) {
		C=colors;
		MINUS(memo);
		return val(0,colors.size()-1);
	}
};

まとめ

どこかで似たような問題見たな…と思ったら豹本にあった「ビジネス握手」だね。
向こうはペンギンの色属性はないし、組み合わせ数を求める問題だけど、処理範囲を分割していくのは同じ。