自动搬运

查看原文

来自洛谷，原作者为

	JK_LOVER 却顾所来径，苍苍横翠微。

搬运于2025-08-24 22:19:23，当前版本为作者最后更新于2020-08-24 20:13:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

给你 $n$ 个字符串，插入字典树中，要求如何重构串，使字典树节点最小。$QAQ$

分析

$n\le 16$ 可以考虑状压 $dp$ 。考虑如何计算字典树的节点数。如果是两个串，那么 $Size = len_{s_1}+len_{s_2}-pre_{1,2}$ 。 $pre_{i,j}$ 表示 $s_1,s_2$ 的前缀长度。那么将这个拓展到多个字符串。令 $dp[s]$ 表示，已经插入集合为 $s$ 时最小节点数。

那么这道题就做完了，要记住最后还要加上空节点 $1$ 个。

• 为什么不用 $dp[s] = dp[s-i]+len_{s_i}-pre_{i..j}$ 这种转移方程。我考虑的是，这样转移是没有考虑到所以状态的，如果各位有想法欢迎私聊。

时间复杂度为 $O(3^n + n\times 2^n)$ 。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
char ch[N];
int pre[N][30],sum[20][30],n,f[N];
int main(){
	cin >> n;
	memset(f,0x3f,sizeof(f));memset(pre,0x3f,sizeof(pre));
	for(int i = 1;i <= n;i++){
		cin >> ch+1;
		for(int j = strlen(ch+1);j;j--) sum[i][ch[j]-'a'+ 1]++;
		sum[i][0] = strlen(ch+1);
		f[1<<i-1] = sum[i][0];
	}
	for(int s = 1;s < (1<<n);s++){
		for(int i = 1;i <= n;i++){
			if((s>>i-1)&1){
				for(int j = 1;j <= 26;j++) pre[s][j] = min(pre[s][j],sum[i][j]); 
			}
		}
		pre[s][0] = 0;
		for(int i = 1;i <= 26;i++) pre[s][0] += pre[s][i];
		for(int S = s&(s-1);S;S = (S-1)&s) {
			f[s] = min(f[s],f[S]+f[S^s]-pre[s][0]);
		}
	}
	cout << f[(1<<n)-1]+1 << endl;
}