[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;
}