题面
给出 $n$个互不包含的字符串,要求你求出一个最短的字符串 $S$,使得这 $n$ 个字符串在 $S$ 中总共至少出现$m$次,问 $S$ 最短是多少。
思路
把题目转化一下,求出$F[i][j]$表示把$S[j]$接在$S[i]$后面的代价,这个用$substr$比较或者$hash$都可以,然后我们得到了一个矩阵$F$。设一个矩阵$A$,大小为$[n]$,$A[i]$表示为出现了$x$个字符串并且以$S[i]$结尾的最小长度,$x$即为变换次数。考虑单次变换$A[1-n]$会与$F[1-n][i]$变化加法取$min$即为在每个现有以$S[1-n]$结尾的字符串后添加$S[i]$的最小长度,也就是A*F=A’,$A'[i]=min(A[k]+F[k][i],A'[i])$这也就是$floyd$,简单矩阵快速幂即可。
注意点
$darkbzoj$的题面莫得说互不包含,害我思考了好久包含怎么办(如果包含则一次变换不一定使得出现次数只加$1$,可能加更多)
代码
#include<bits/stdc++.h>
#define LL long long
using namespace std;
string s[205];
LL n,m,b[205][205],a[2][205],Min=99999999999999,res[205][205];
inline void read(LL &x)
{
LL f=1;x=0;char ch=getchar();
while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while (isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
x*=f;
}
inline void mul(LL a[205][205],LL b[205][205],LL c[205][205])
{
LL tmp[205][205];
for (LL i=1;i<=n;i++) for (LL j=1;j<=n;j++) tmp[i][j]=99999999999999;
for (LL i=1;i<=n;i++)
{
for (LL j=1;j<=n;j++)
{
for (LL k=1;k<=n;k++)
tmp[i][j]=min(tmp[i][j],a[i][k]+b[k][j]);
}
}
for (LL i=1;i<=n;i++) for (LL j=1;j<=n;j++) c[i][j]=tmp[i][j];
}
inline void mull(LL a[2][205],LL b[205][205],LL c[2][205])
{
LL tmp[2][205];
for (LL i=1;i<=1;i++) for (LL j=1;j<=n;j++) tmp[i][j]=99999999999999;
for (LL i=1;i<=1;i++)
{
for (LL j=1;j<=n;j++)
{
for (LL k=1;k<=n;k++)
tmp[i][j]=min(tmp[i][j],a[i][k]+b[k][j]);
}
}
for (LL i=1;i<=1;i++) for (LL j=1;j<=n;j++) c[i][j]=tmp[i][j];
}
inline LL calc(LL x,LL y)
{
LL lenx=s[x].size()-1,leny=s[y].size()-1;
if (x!=y) {for (LL i=min(lenx,leny)+1;i>=1;i--) if (s[x].substr(lenx-i+1,i)==s[y].substr(0,i)) return i;}
else for (LL i=min(lenx,leny);i>=1;i--) if (s[x].substr(lenx-i+1,i)==s[y].substr(0,i)) return i;
return 0;
}
inline void ksm(LL base[205][205],LL index)
{
for (int i=1;i<=n;i++)for (int j=1;j<=n;j++)res[i][j]=base[i][j];
while (index)
{
if (index&1) mul(res,base,res);
mul(base,base,base);
index>>=1;
}
}
int main()
{
read(n),read(m);
for (LL i=1;i<=n;i++) cin>>s[i];
for (LL i=1;i<=n;i++) for (LL j=1;j<=n;j++) b[i][j]=s[j].size()-calc(i,j);
// for (LL i=1;i<=n;i++)
// {
// for (LL j=1;j<=n;j++) cout<<b[i][j]<<" ";
// cout<<endl;
// }
for (LL i=1;i<=n;i++) a[1][i]=s[i].size();
m--;
if (m==0) {for (LL i=1;i<=n;i++) Min=min(Min,a[1][i]);cout<<Min<<endl;return 0;}
ksm(b,m-1);
mull(a,res,a);
for (LL i=1;i<=n;i++) Min=min(Min,a[1][i]);cout<<Min<<endl;return 0;
return 0;
}