题解【P6289 [COCI2016-2017#1] Vještica】

传送门。

$\texttt{Description}$

给定 $n$ 个字符串，你可以将任意个字符串重组，使得存储这些单词的 $\text{Trie}$ 数的节点数尽量小。$1\le n\le 16$。

$\texttt{Solution}$

第一眼发现 $n\le 16$，可以考虑状压 $\texttt{DP}$。

我们设 $f[s]$ 表示插入完集合 $s$ 中的所有字符串的最小节点数。

那么显然答案是 $f[S]$，$S$ 表示所有字符串的集合。

考虑转移。

先解决一种简单的情况，假设说只有两个字符串 $A,B$，那么将它们插入到 $\text{Trie}$ 树上后所需的节点数为 $len_A+len_B-\text{same}(A,B)$，$\text{same}(A,B)$ 指 $A$ 和 $B$ 可能的最长公共前缀。

这种简单的情况是可以推广到 $n$ 个字符串的。

对于 $f[s]$，我们考虑枚举 $s$ 的子集 $s'$，那么 $s\operatorname{xor} s'$ 是 $s$ 的另一个子集 $s''$。

我们直接对于 $s'$ 和 $s''$ 看做两个字符串，长度分别为 $f[s']$ 和 $f[s'']$，所以就可以归结为两个字符串的情况。

于是得到了最终的状态转移方程：$f[s]=\min_{s'\in s}\{f[s']+f[s\operatorname{xor} s']-\operatorname{same}(s)\}$。

考虑函数 $\operatorname{same}$ 如何求。

我们贪心的想，对于一个字符 $c$，我们考虑集合中所有字符串中 $c$ 的数量，找到最小的那一个，记为 $x$，是不是说明公共的长度又能减少 $x$，因为所有的字符串都有这 $x$ 个字符 $c$。我们对于每一个字符都求一遍相应的 $x$，求和，便是 $\operatorname{same}(s)$ 的值。

细节留给读者自行处理。

贴一下代码：

#include
#include
using namespace std;
const int MAXN(18);
const int MAXM(1e6+10);
const int INF(1e9+10);
int n;
char s[MAXN][MAXM]; 
int fac[MAXN],len[MAXN];
inline int lowbit(int x){return x&(-x);}
inline int Min(int x,int y){return x

$$\texttt{The End.by UF}$$