Trie 树
PROBLEM
题目描述
字母（Trie）树是一个表示一个字符串集合中所有字符串的前缀的数据结构，其有如下特征：
1.树的每一条边表示字母表中的一个字母
2.树根表示一个空的前缀
3.树上所有其他的节点都表示一个非空前缀，每一个节点表示的前缀为树
根到该节点的路径上所有字母依次连接而成的字符串。
4.一个节点的所有出边（节点到儿子节点的边）中不存在重复的字母。
现在Matej手上有N个英文小写字母组成的单词，他想知道，如果将这N个单词中的字母分别进行重新排列，形成的字母树的节点数最少是多少。
输入
第一行包含一个正整数N（1<=N<=16）
接下来N行每行一个单词，每个单词都由小写字母组成。
单词的总长度不超过1,000,000。
输出
输出仅一个正整数表示N个单词经过重新排列后，字母树的最少节点数。
样例输入
3
a
ab
abc
样例输出
4
SOLUTION
n<16 枚举所有状态。对每个状态枚举子集（for j = （i-1)&i ; j ; j = (j-1)&i）
状态转移：f[i] = min(f[i],f[j]+f[i^j]-sum); sum是当前状态下所有字母在每个字符串中数量的最小值的和。
CODE
#define IN_PC() freopen("C:\\Users\\hz\\Desktop\\in.txt","r",stdin)
#define IN_LB() freopen("C:\\Users\\acm2018\\Desktop\\in.txt","r",stdin)
#define OUT_PC() freopen("C:\\Users\\hz\\Desktop\\out.txt","w",stdout)
#define OUT_LB() freopen("C:\\Users\\acm2018\\Desktop\\out.txt","w",stdout)
#include<bits/stdc++.h>
using namespace std;
const int MAXN = 20;
const int MAXLEN = 1000005;
char s[MAXLEN];
int lenthS[MAXN];
int cntAlp[MAXN][26];
int f[1<<MAXN];
int main()
{
// IN_PC();
int n;
scanf("%d",&n);
for(int i=0;i<n;i++){
scanf("%s",s);
lenthS[i] = strlen(s);
for(int j=0;s[j];j++){
cntAlp[i][s[j]-'a']++;
}
}
for(int i=1;i<(1<<n);i++){
for(int j=0;j<n;j++){
if(i&(1<<j)){
f[i]+=lenthS[j];
}
}
int sum = 0;
for(int k=0;k<26;k++){
int minv = MAXLEN;
for(int j=0;j<n;j++){
if(i&(1<<j)){
minv = min(minv,cntAlp[j][k]);
}
}
sum+=minv;
}
for(int j=(i-1)&i;j;j=(j-1)&i){
f[i] = min(f[i],f[j]+f[i^j]-sum);
}
}
cout<<f[(1<<n)-1]+1<<endl;
}