Luogu P6269 [COCI2016-2017#1] Vještica 题解

题目传送门

题目描述 Matej 面临着一个难题。在此之前，我们必须熟悉一种称作前缀树（trie）的数据结构。前缀树以前缀的方式，储存单词：

前缀树的每一条边都用英文字母表中的字母表示。前缀树的根节点表示空前缀。前缀树的每个其他节点都表示一个非空前缀。依次连接根节点至该节点路径上所标有的字母，即可得到该前缀。不存在从一个节点出发的、标有相同字母的两条边。

例如，这棵前缀树储存了 A,to,tea,ted,ten,i,in,inn：

现在，Matej 获得了 nn 个单词，并可以将其中的一些单词重组。例如 abc 可以重组为 acb,bac,bca,cab,cba 。请你计算，将一些单词重组后，储存这些单词的前缀树节点数的最小值。

输入格式 第一行一个整数 $n$ 。 接下来 $n$ 行，每行一个字符串，表示 Matej 获得的单词。

输出格式 一行，一个整数，表示将一些单词重组后，储存这些单词的前缀树节点数的最小值。

输入输出样例 #1 输入

3 a ab abc

#1 输出

4

#2 输入

3 a ab c

#2 输出

4

#3 输入

4 baab abab aabb bbaa

#3 输出

5

说明/提示 样例 3 解释 所有单词均可以重组为 aabb。显然，前缀树最少的节点数应为 55（包含了表示空前缀的根节点）。 数据规模与约定 对于 $100\%$ 的数据，保证 $1\le n\le 16$。 所有单词的长度和不超过 $10^6$ ，且只包含小写字母。 说明 题目译自 COCI2016-2017 CONTEST #1 T6 Vještica。

题目解析

首先，可以贪心，可以搜索，并且不需要输出路径，考虑DP。 $n\le 16$ ，这么小肯定是状压DP。 令 $f_i$ 代表状态为 $i$ 时的答案，这里把 $i$ 看做一个集合。 首先考虑的是 $i$ 只有两项的时候，不难发现， $f_{\{i,j\}}=f_i+f_j-pr{e}_{i,j}$ ，其中 $pr{e}_{i,j}$ 表示 $i,j$ 的最长公共字串。 拓展一下，得出 $f_i=f_{i-j}+f_j-pr{e}_{x,y}\left(x,y\in i\right)$ 这里需要注意一下循环的范围。 最后注意一下要把结果加上 $1$ ，因为还有一个空节点。

代码：

#include<cstdio> //luogu P6289 #include<cstring> #include<iostream> #define maxn 70039 using namespace std; inline int read(){ char c=getchar(); int sum=0,flag=0; while((c<'0'||c>'9')&&c!='-') c=getchar(); if(c=='-') c=getchar(),flag=1; while('0'<=c&&c<='9'){ sum=(sum<<1)+(sum<<3)+(c^48); c=getchar(); } if(flag) return -sum; return sum; } int f[maxn],pre[maxn][39]; int sum[39][39]; char s[100039]; int n,len; int main(){ cin>>n; memset(f,0x3f,sizeof(f)); memset(pre,0x3f,sizeof(pre)); for(int i=1;i<=n;i++){ cin>>s; len=strlen(s); for(int j=0;j<len;j++) sum[i][s[j]-'a'+1]++; sum[i][0]=strlen(s); f[1<<i-1]=sum[i][0]; } for(int i=1;i<(1<<n);i++){ for(int j=1;j<=n;j++){ if((i>>j-1)&1){ for(int k=1;k<=26;k++) pre[i][k]=min(pre[i][k],sum[j][k]); } } pre[i][0]=0; for(int k=1;k<=26;k++) pre[i][0]+=pre[i][k]; for(int j=(i-1)&i;j;j=(j-1)&i) f[i]=min(f[i],f[i^j]+f[j]-pre[i][0]); } printf("%d",f[(1<<n)-1]+1); return 0; }