题意

给出n个字符串，每个字符串的字符可以任意调换位置，问将这些字符串建一棵trie树需要的最少节点数（包括根节点）。 n<=16,字符串总长<=10000000

分析

咋一看啥思路都没有，其实并不难，说白了还是我太弱啦。。。 复制一波题解： 显然，如果我们希望 Trie 树的节点数尽量少，我们应该先将所有单词公共的字母拿出 来，作为 Trie 树最上几层的初始链。比如说我们有 aaab，baab 和 cab 三个单词，我们会将 ab 挑出来，然后剩下的单词就变成了 aa，ab，c。 对于剩下的单词，我们将其分成两个子集，（aa，ab）和（c），并分别再计算最长的公 共字母链。显然，当集合中有 n 个单词时，有 2 n种方式将这些单词分成两个子集。 由此，我们可以用状态压缩 dp 解决这个问题。一个状态由单词的子集来描述，也就是 说我们有 2 n个状态，并计算每一种子集形成 Trie 树需要的最少节点数，转移时枚举如何将 子集分裂成两个更小的子集，即可解决整个问题。整个算法总的时间复杂度为 O(3n)$O(3^n)$。

顺带发一波枚举i的子集的方法：for (int j=i;j;j=(j-1)&i); 这样就可以枚举所有i的子集啦。

代码