upc 6902: Trie树 （状压dp）

6902: Trie树

时间限制: 1 Sec  内存限制: 128 MB
提交: 137  解决: 19
[提交] [状态] [讨论版] [命题人:admin]

题目描述

字母（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

来源/分类

中山纪念中学20170304 

【小结】

状压dp配字符串。我怎么这么菜

【分析】

如果只有两个字符串（注意我这里形容的字符串字母乱序），abc 和 abe，很明显能找到最长的公共前缀为ab长度2，故答案为3+3-2

对于多个字符串，可分为两组，假设每一组都已经得到了最优值，那么总的最优值就等于这两组值之和减掉最长公共前缀

一直分组，最后一定可以分解成每组一个字符串，合并时，按上述方法取最小值即可。

状压dp把n个物品对应到一个数字二进制的每一个位，为1代表选上，为0代表不选。

【代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAX=2e5+5;
const int INF=0x3f3f3f3f;
template<class T>bool gmax(T &a,T b){return a<b?a=b,1:0;}
template<class T>bool gmin(T &a,T b){return a>b?a=b,1:0;}

char str[MAX*5];
int dp[1<<17];
int cnt[17][26]; //每个串中，各字母数量
int c[26];
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%s",str);
        for(int j=0;str[j];j++)
            cnt[i][str[j]-'a']++;
    }

    for(int i=0;i<(1<<n);i++) //枚举集合
    {
        dp[i]=0;
        memset(c,0x3f,sizeof(c));
        for(int j=0;j<n;j++)if((1<<j)&i) //枚举i集合内的单词
        {
            for(int ch=0;ch<26;ch++)
            {
                dp[i]+=cnt[j][ch]; //统计当前集合所有字母数，这有可能是最坏情况，没有公共前缀
                gmin(c[ch],cnt[j][ch]); //统计每个字母的最小出现次数，若不为0，则可以作为公共前缀
            }
        }
        int sum=0;
        for(int j=0;j<26;j++)sum+=c[j]; //统计公共前缀的数量
        for(int j=i&i-1;j;j=i&j-1)
            gmin(dp[i],dp[j]+dp[j^i]-sum); //j是i的一个子集，j^i是j的补集,合并后可减掉公共前缀
    }
    printf("%d\n",dp[(1<<n)-1]+1);
}