[COCI] Vje š TICA (subset DP)

The question ：

Given $n(n\le 16)$ A string . You can arrange the letters in the string at will , So that the number of nodes after inserting these strings into the dictionary tree is the least .
The total length of the string shall not exceed $10^6$.

Ideas ：

Only $16$ position , Consider the state pressure representation set .
use $DP((10111{)}_2)$ It means the first one $1,3,4,5$ The minimum number of knots after the string is inserted .

First consider inserting two strings into the dictionary tree , The number of nodes contributed is the sum of the number of nodes of two strings minus the prefix of two strings .
therefore , We consider that the prefix of two strings should be the longest , Is the number of each letter $min$ And .

Then consider a few strings $"aabc","aabb"."abc"$. Can greedily take out $"ab"$ Put it in the front , Then left $"ac","ab"."c"$ Think again .

use $PRE(S)$ Represents a collection $S$ The longest common prefix of all strings in , Consider from $("ac","ab")$ and $("c")$ Merge into $("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")$

So let's consider $S$ From its subset $A$ Turn around , There is $DP(S)=DP(A)+DP(S-A)+PRE(S)$.
Then you can do subsets $dp$ 了 , Complexity $o(3^n)$.

Code ：

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