【题解】LuoGu6289：Vještica

原题传送门
这题可以想出很多性质
$n<=16$暗示的非常明显，我后来才意识到是状压

对于一堆字符串，显然，我们可以先把它们共有的部分弄掉，剩下的不存在共有的部分

我可以状压$d{p}_i$表示状态$i$的答案
枚举$i$的子集$j$，表示先把$j$和$i-j$内部先算好答案

所以两部分的答案加起来的时候总共共有的部分重复算了一遍
要减掉
令$sum=总共的共有部分$
$d{p}_i=min(d{p}_j+d{p}_{i-j}-sum)$

Code：

#pragma GCC optmize("-Ofast")
#include <bits/stdc++.h>
#define maxn 1000010
using namespace std;
int a[20][30], n, dp[maxn], power[25];
char s[maxn];

int calc(int sta){
	int sum = 0;
	for (int i = 1; i <= 26; ++i){
		int x = 1e9;
		for (int j = 1; j <= n; ++j)
			if (power[j - 1] & sta) x = min(x, a[j][i]);
		sum += x;
	}
	return sum;
}

int main(){
	freopen("vjestica.in", "r", stdin);
	freopen("vjestica.out", "w", stdout);
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i){
		scanf("%s", s + 1);
		for (int j = 1; j <= strlen(s + 1); ++j) ++a[i][s[j] - 96];
	}
	power[0] = 1;
	for (int i = 1; i <= n; ++i) power[i] = power[i - 1] << 1;
	for (int i = 1; i < power[n]; ++i){
		if (i - (i & -i) == 0){
			dp[i] = calc(i);
			continue;
		}
		int sum = calc(i);
		dp[i] = 1e9;
		for (int j = (i - 1) & i; j; j = (j - 1) & i)
			dp[i] = min(dp[i], dp[j] + dp[i ^ j] - sum);
	}
	printf("%d\n", dp[power[n] - 1] + 1);
	return 0;
}