NKOJ 4191 Trie （状压dp）

发表于 |
字数统计: 767字 | 阅读时长 ≈ 3min

P4191中山纪念中学 Trie

问题描述

字母（Trie）树是一个表示一个字符串集合中所有字符串的前缀的数据结构，其有如下特征：

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

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

输入格式

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

输出格式

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

样例输入

10
jgda
dbfdjj
hehegdfh
faeejic
acagdgfcjc
jifiigdbif
fdbdii
ch
c
adccdd

样例输出

42

此题题目是trie，但是和trie没有什么太大关系，只需要知道，对于这些串，将他们的公共部分作为公共前缀是最优的即可。
那么首先考虑两个串，答案显然是他们的长度和减去公共部分。
那么再考虑三个串，显然可能出现两两的公共部分大于三个的公共部分的情况，这种时候trie树必然会出现分叉，我们需要考虑如何分叉，分成二叉或三叉，再者哪些串在同一子树上，既然一定会分成多颗子树，那么我们可以直接将这三个串拆成两个子集，先求出两个子集的最优解，然后减去公共部分即可。
也就是说，令$F[S]$表示将$S$集合中的字符串弄到一棵树上的最少节点数，那么有
$F[S]=min{ F[k]+F[S\ xor\ k] }-S中字符串的公共部分长度$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<cstring>
#define N 66666
#define M 1000005
using namespace std;
int n,S,F[N],cnt[20][200],A[200],sum;
char s[M];
int main()
{
	int i,j,k;
	scanf("%d",&n);
	S=(1<<n)-1;
	for(i=1;i<=n;i++)
	{
		scanf("%s",&s);
		k=strlen(s);
		for(j=0;j<k;j++)cnt[i][s[j]]++;
	}
	for(i=1;i<=S;i++)
	{
		memset(A,60,sizeof(A));sum=0;
		for(j=1;j<=n;j++)
		if(i&(1<<j-1))
		{
			for(k='a';k<='z';k++)
			{
				F[i]+=cnt[j][k];
				A[k]=min(A[k],cnt[j][k]);
			}
		}
		for(j='a';j<='z';j++)sum+=A[j];
		for(j=i&i-1;j;j=i&j-1)F[i]=min(F[i],F[i^j]+F[j]);
		if(F[i]>sum)F[i]-=sum;
	}
	printf("%d",F[S]+1);
}