[COCI] Vještica （子集dp）

题意：

给定$n(n\le 16)$个串。你可以把串内的字母任意排列，使得将这些串插入字典树后的结点最少。 串总长不超过$10^6$.

思路：

只有$16$位，考虑状压表示集合。 用$DP((10111{)}_2)$表示第$1,3,4,5$串被插入后的最小结点数。

先考虑两个串插入字典树，贡献的结点数是两个串的结点数之和减去两个串的前缀。 所以，我们考虑两个串的前缀要最长，就是每个字母的个数取$min$的和。

那么考虑几个串$"aabc","aabb"."abc"$。可以贪心地拿出$"ab"$放前面，然后剩下$"ac","ab"."c"$再进行考虑。

用$PRE(S)$表示集合$S$中所有串的最长公共前缀，考虑从$("ac","ab")$和$("c")$合并到$("ac","ab","c")$。 $DP("aabc","aabb","abc")$ $=DP("ac","ab","c")+PRE(“aabc”,"aabb"."abc")$ $=DP("ac","ab")+DP("c")+PRE("aabc",“aabb”,"abc")$ $=DP("aabc","aabb")-PRE("ab","ab")+DP("abc")-PRE("ab")+PRE("aabc",“aabb”,"abc")$ $=DP("aabc","aabb")+DP("abc")-PRE("aabc",“aabb”,"abc")$

那么我们考虑$S$从它的子集$A$转移过来，就有$DP(S)=DP(A)+DP(S-A)+PRE(S)$。 然后就可以做子集$dp$了，复杂度$o(3^n)$。

代码：

#include <bits/stdc++.h> using namespace std; typedef long long ll; int num1[1000005]; int getNum(int x) { if(num1[x])return num1[x]; int ans=0; while(x!=0) { x-=x&-x; ans++; } return num1[x]=ans; } int len[20]; int num[20][26]; char ss[1000005]; int n; int pre(int s) { int nu[26]; for(int i=0;i<26;i++)nu[i]=1e9; for(int i=0;i<n;i++)if((s>>i)&1) { for(int j=0;j<26;j++)nu[j]=min(nu[j],num[i][j]); } int sum=0; for(int i=0;i<26;i++)sum+=nu[i]; return sum; } int dp[1000005]; int main() { scanf("%d",&n); for(int i=0;i<n;i++) { scanf("%s",ss); len[i]=strlen(ss); for(int j=0;j<len[i];j++)num[i][ss[j]-'a']++; } for(int s=1;s<1<<n;s++) { dp[s]=1e9; if(getNum(s)==1) { for(int i=0;i<n;i++)if((s>>i)&1)dp[s]=len[i]; continue; } int preS=pre(s); for (int i=(s-1)&s;i;i=(i-1)&s) { dp[s]=min(dp[s],dp[i]+dp[s^i]-preS); } } printf("%d\n",dp[(1<<n)-1]+1); return 0; }