TopCoder SRM 330 Div1 Medium PrefixFreeSubsets

問題

文字列の集合がprefix-freeであるとは、
どの文字列も、他の文字列の接頭辞となっていないことをいう。

空の文字列もprefix-freeである。

文字列の集合が与えられる。
この集合の部分集合（空集合および、元の集合そのものも含む）のうち、prefix-freeであるものはいくつあるか、求めよ。

制約条件

集合の要素≦50
各文字列の長さ≦50
集合の要素は全て互いに異なる

方針

文字列jが、文字列iの接頭辞であるとき、i→jに辺を張ったグラフを考える。
ただし、別の文字列kがあって、i→k→jと接頭辞になっているときはi→jには辺を張らない。

このグラフは森になる。
このグラフ上の、安定集合が求める集合である。
これは木のDPをすればいい。

木のDPは、根を使う場合が1通りと、
根を使わない場合が、それぞれの子の場合の数を掛け合わせたものになるので、メモ化再帰をすればいい。

ソースコード

bool prefix(string a,string b){
	return a.size()<b.size()&&a==b.substr(0,a.size());
}
int n,deg[50];
bool pre[50][50];
ll dp[50];
ll rec(int c){
	if(dp[c]>=0)return dp[c];
	dp[c]=1;
	rep(i,n)if(pre[c][i])dp[c]*=rec(i);
	dp[c]+=1;
	return dp[c];
}
class PrefixFreeSubsets {
	public:
	long long cantPrefFreeSubsets(vector <string> words) 
	{
		memset(pre,0,sizeof(pre));
		memset(deg,0,sizeof(deg));
		memset(dp,-1,sizeof(dp));
		
		n=words.size();
		rep(i,n)rep(j,n)if(prefix(words[i],words[j])){
			rep(k,n)if(prefix(words[i],words[k])&&prefix(words[k],words[j]))goto FAIL;
			pre[i][j]=1;
			deg[j]++;
			FAIL:;
		}
		ll ans=1;
		rep(i,n)if(deg[i]==0)ans*=rec(i);
		
		return ans;
	}