Trie树 (状压DP)

题目描述

字母（Trie）树是一个表示一个字符串集合中所有字符串的前缀的数据结构，其有如下特征：
1.树的每一条边表示字母表中的一个字母
2.树根表示一个空的前缀
3.树上所有其他的节点都表示一个非空前缀，每一个节点表示的前缀为树
根到该节点的路径上所有字母依次连接而成的字符串。
4.一个节点的所有出边（节点到儿子节点的边）中不存在重复的字母。

 

单词“A”“to”“tea”“ted”“ten”“i”“in”“inn”对应的Trie树

现在Matej手上有N个英文小写字母组成的单词，他想知道，如果将这N个单词中的字母分别进行重新排列，形成的字母树的节点数最少是多少。

输入

第一行包含一个正整数N（1<=N<=16）
接下来N行每行一个单词，每个单词都由小写字母组成。
单词的总长度不超过1,000,000。

输出

输出仅一个正整数表示N个单词经过重新排列后，字母树的最少节点数。

样例输入

3
a
ab
abc

样例输出

 4

无脑排序建字典树输出cnt，然后发现根本就不是字典树的题目啊，然后发现N == 16，明显可以状压，然后就没有了然后。可以想到状压，但是并无法找到状态转移，0代表不选，1代表选择选择，怎么用前面得到的最优解去更新后面出现的值，所以果断认为这题属于不看题解不会系列。看了题解之后，也理解了半天，最后打出枚举子集的表，才敢相信这算法的神奇。不看半天题，都不好意思AC。

首先从最基础的两个单词看起：当两个单词的相同字母尽量多的时候，此时的Tire树的节点数是最少的。但是可以发现，当单词数目>=3的时候，此结论是不成立的，那么可不可以当单词数>=3时，分成若干个两两相交的状态，从而得到最优解呢？答案是可以的，这就是位运算神奇的地方。

然后考虑枚举每个状态子集的两个状态，这两种状态无非是将当前状态的每一位的1分到两个子状态里面，但是要确保两个子状态的当前位不同时为1，然后，下面这句话即可完成枚举状态: for(j = i;j;j = (j-1)&i)

最后考虑DP部分，根据一开始的分析，很容易得到状态转移，找到所有串的公共部分sum，用最后枚举得到的dp[i]跟sum做差，得到当前的最优状态。状态需要从小的集合到大的集合过渡，只有子结构最优的前提下，才能得到最优的当前状态，然后考虑dp[i] == sum的时候，说明此时的所有选择的串都相同，也就不存在需要减去的情况，故只有当dp[i] > sum时，才需要dp[i]-sum。

最后需要结果+1.字典树的根节点是空值。收获：高效枚举子状态for(j = i;j;j = (j-1)&i)

部分细节见代码：
 

/*
Look at the star
Look at the shine for U
*/ 

#include<bits/stdc++.h>
#define sl(x) scanf("%lld",&x)
using namespace std;
typedef long long ll;
const int N = 1e6+5;
const ll mod = 1e9+7;
const int INF = 0x3f3f3f3f;
int dp[N],vis[30][30],len[N];
char s[N];
int main()
{
	int n,i,j,k;
	scanf("%d",&n);
	for(i = 0;i < n;i++)
	{
		scanf("%s",s); len[i] = strlen(s);
		for(j = 0;s[j];j++) vis[i][s[j]-'a']++;     //记录第i串，每个字母出现的次数 
	}
	int temp = (1<<n);
	for(i = 0;i < temp;i++)    //状态
	{
		int sum = 0;
		for(j = 0;j < n;j++) if((1<<j)&i) dp[i] += len[j];      //最多需要的节点数
		//统计每个字符串中公共单词的个数
		for(j = 0;j < 26;j++)
		{
			int minn = INF;
			for(k = 0;k < n;k++) if((1<<k)&i) minn = min(minn,vis[k][j]);
			sum += minn;
		}
		for(j = i;j;j = (j-1)&i)
        {
            dp[i] = min(dp[i],dp[j]+dp[i^j]);
        //    cout<<"i = "<<i<<"       "<<j<<"<--->"<<(i^j)<<endl;
        }
        if(dp[i] > sum) dp[i] -= sum;
	}
	printf("%d\n",dp[(1<<n)-1]+1);
}