题解 P6289 【[COCI2016-2017#1] Vještica】
JK_LOVER
·
·
题解
题意
给你 n 个字符串，插入字典树中，要求如何重构串，使字典树节点最小。QAQ
分析
$$
dp[s] = dp[s-S] +dp[S] -pre_{i..j} \ (i,j\in s)
$$
那么这道题就做完了，要记住最后还要加上空节点 $1$ 个。
- 为什么不用 $dp[s] = dp[s-i]+len_{s_i}-pre_{i..j} $ 这种转移方程。我考虑的是，这样转移是没有考虑到所以状态的，如果各位有想法欢迎私聊。
时间复杂度为 $O(3^n + n\times 2^n)$ 。
## 代码
```cpp
#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;
}
```