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; } };