【问题描述】
字母（Trie）树是一个表示一个字符串集合中所有字符串的前缀的数据结构，其有如下特征：
1.树的每一条边表示字母表中的一个字母 2.树根表示一个空的前缀 3.树上所有其他的节点都表示一个非空前缀，每一个节点表示的前缀为树根到该节点的路径上所有字母依次连接而成的字符串。 4.一个节点的所有出边（节点到儿子节点的边）中不存在重复的字母。 现在Matej手上有N个英文小写字母组成的单词，他想知道，如果将这N个单词中的字母分别进行重新排列，形成的字母树的节点数最少是多少。
【输入格式】
第一行包含一个正整数N（1<=N<=16） 接下来N行每行一个单词，每个单词都由小写字母组成。 单词的总长度不超过1,000,000。
【输出格式】
输出仅一个正整数表示N个单词经过重新排列后，字母树的最少节点数。
【输入样例】
【样例1】 3 a ab abc
【样例2】 3 a ab c
【样例3】 4 baab abab aabb bbaa
【输出样例】
【样例1】 4
【样例2】 4
【样例3】 5
【数据范围】
【样例解释3】 所有的单词都可以排列成aabb，对应的Trie树节点数为5。
【来源】
https://jzoj.net
这道题我一开始就只做了个贪心（完全是乱贪），晚上脑子不好用，乱做了一通。 正确的做法应该是一道集合动规的题，对于集合动规因个人习惯都用的记忆化搜索。 用2个数组g（i，j）记录第i中情况中第j个字母有几个。 d（i）第i中情况的最小话费。 然后枚举每一个情况的子情况进行搜索就可以得到答案了。 如果不优化其实还是只有30分左右。 优化如下：
t=(i&x); if(t!=i) { t=i-t; i+=t-1; continue; }这段代码大多集合动规都可以用来优化，而且优化的很多。 其实就是直接跳过所有不包含的情况。
完整代码如下：
#include<cstdlib> #include<cstdio> #include<cstring> #include<iostream> using namespace std; const int maxn=1<<17; const int inf=200000005; int d[maxn]={0}; int a[20][30],n,g[maxn][30]={0},b[20]; char s[1000005]; int run(int x) { if(d[x]) return d[x]; d[x]=inf; int ans=inf,t; for(int i=1;i<=x/2;i++) { t=(i&x); if(t!=i) { t=i-t; i+=t-1; continue; } d[x]=min(d[x],run(i)+run(x-i)); if(ans==inf) { ans=0; for(int k=0;k<26;k++) { g[x][k]=min(g[i][k],g[x-i][k]); ans+=g[x][k]; } } } if(ans==inf) ans=0; return d[x]=d[x]-ans; } int main() { //freopen("in.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d",&n); int k; b[1]=1; for(int i=2;i<=n;i++)b[i]=b[i-1]*2; for(int i=1;i<=n;i++) { scanf("%s",s); for(k=0;s[k]!=0;k++) a[i][s[k]-'a']++,g[b[i]][s[k]-'a']++; d[b[i]]=k; } k=1<<n; cout<<run((1<<n)-1)+1; return 0; }