题目传送门

前置知识

前缀函数与 KMP 算法 | 状压 DP

解法

由于 \(\sum\limits_{i=1}^{n} |S_{i}|\) 极大且不需要记录路径，所以 luogu P2322 [HNOI2006] 最短母串问题 的枚举所有可能的字符串 \(T\) 进行判断不可做。

设 \(f_{i,j}\) 表示当“字符串包含状态”对应的二进制数为 \(i\) 时，且结尾为 \(j\) 时的最小长度，状态转移方程为 \(f_{i,j}= \min\limits_{j \ne k}^{} \{f_{i-2^{j},k}-g_{k,j}+|S_{j}| \}\)，其中 \(g_{k,j}\) 表示 \(S_{k}\) 的后缀和 \(S_{j}\) 的前缀匹配的最长长度，且状态 \(i\) 中包含 \(j,k\)。

\(g\) 数组可以用 KMP 维护。

注意去重和删去在其他字符串中已被包含的字符串。

代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define ull unsigned long long
#define sort stable_sort 
#define endl '\n'
int nxt[200010],f[(1<<22)+10][22],g[22][22];
string s[22],ss[22],t;
int main()
{
	int m,n=0,ans=0x7f7f7f7f,flag,i,j,k,x,y;
	cin>>m;
	memset(f,0x3f,sizeof(f));
	for(i=0;i<=m-1;i++)
	{
		cin>>ss[i];
	}
	sort(ss+0,ss+m);
	m=unique(ss+0,ss+m)-ss;
	for(i=0;i<=m-1;i++)
	{
		flag=0;
		for(j=0;j<=m-1;j++)
		{
			if(i!=j&&ss[j].find(ss[i])!=string::npos)
			{
				flag=1;
				break;
			}
		}
		if(flag==0)
		{
			s[n]=ss[i];
			n++;
		}
	}
	for(x=0;x<=n-1;x++)
	{
		for(y=0;y<=n-1;y++)
		{
			if(x!=y)
			{
				t=' '+s[y]+'#'+s[x];
				for(i=2,nxt[1]=j=0;i<t.size();i++)
				{
					while(j>=1&&t[i]!=t[j+1])
					{
						j=nxt[j];
					}
					j+=(t[i]==t[j+1]);
					nxt[i]=j;
				}
				g[x][y]=nxt[t.size()-1];
			}
		}
	}
	for(i=0;i<=n-1;i++)
	{
		f[(1<<i)][i]=s[i].size();
	}
	for(i=0;i<=(1<<n)-1;i++)
	{
		for(j=0;j<=n-1;j++)
		{
			if((i>>j)&1)
			{
				for(k=0;k<=n-1;k++)
				{
					if(j!=k&&((i>>k)&1))
					{
						f[i][j]=min(f[i][j],f[i-(1<<j)][k]-g[k][j]+(int)s[j].size());
					}
				}
			}
		}
	}
	for(i=0;i<=n-1;i++)
	{
		ans=min(ans,f[(1<<n)-1][i]);
	}
	cout<<ans<<endl;
	return 0;
}

后记

多倍经验：CF25E Test