TopCoder SRM 491 Div1 Medium PrefixTree

問題

n個の文字列が与えられる。
それぞれの文字列は、文字列の中で文字の順序を自由に入れ替えてよい。


入れ替えた後で、trie木を作る。
文字の順序を最適に入れ替えたとき、trie木の頂点の数は最小でいくつか、求めよ。

制約条件

n≦16
各文字列の長さ≦50

方針

文字列の集合iのtrie木を作るのに必要な頂点の個数をdp[i]とすると、
dp[i] = min{dp[j] + dp[i ^ j] - (iのうち、まとめられる頂点の個数)}
という漸化式が立つ。


まとめられる頂点の個数というのは、iすべてに共通する文字の個数。
この分だけ新しいtrie木の頂点を省略できる。


なので、部分集合を全てなめるようなDPをすれば、全ての文字列をtrie木にするときの必要な頂点の個数が求まる。

ソースコード

int n, dp[1 << 16], same[1 << 16];

class PrefixTree {
	public:
	int getNumNodes(vector <string> words) 
	{
		n = words.size();
		
		for(int i = 1; i < 1 << n; i++){
			same[i] = 0;
			rep(j, 26){
				int mn = inf;
				rep(k, n) if(i & 1 << k)
				mn = min(mn, count(all(words[k]), 'a' + j));
				same[i] += mn;
			}
		}
		
		rep(i, 1 << n) dp[i] = inf;
		rep(i, n) dp[1 << i] = same[1 << i];
		
		rep(i, 1 << n) for(int j = i - 1 & i; j; j = j - 1 & i){
			dp[i] = min(dp[i], dp[i - j] + dp[j] - same[i]);
		}
		return dp[(1 << n) - 1] + 1;
	}
	
};