DTOJ 1587:Hamsters（hamsters）

DTOJ 1587:Hamsters（hamsters）

【题目描述】

Tz养了一群仓鼠，他们都有英文小写的名字，现在Tz想用一个字母序列来表示他们的名字，
只要他们的名字是字母序列中的一个子串就算，出现多次可以重复计算。
现在Tz想好了要出现多少个名字，请你求出最短的字母序列的长度是多少。

【输入】

      输入：第一行n（1<=n<=200）和 m(1<=m<=10^9)，n表示有多少个仓鼠，m表示Tz希望出现名字的次数 接下来n行，每行都是仓鼠的名字（中间没有空格）。

【输出】

一行，最短的字母序列的长度。

【样例输入】

4 5
monika
tomek
szymon
bernard

【样例输出】

23

【分析】

   首先可以处理出v[a][b]表示b接在a后面的长度(即重复部分之前都不算)那么就可以转化成求长度m-1的最短路。假设dis[i][a][b]为经过i步a走到b的最短路，不难得出dis[i][a][b] = min(dis[i/2][a][c] + dis[i-i/2][c][b]) (1<=c<=n)，此时就可以利用快速幂的思想了。前面求v[a][b]可利用hash判断是否一样。

【代码】

#include<bits/stdc++.h>

using namespace std;

const long long inf=1e18;

const int P=1990213;

int n,m,l[210];

long long f[210],g[210],ans=inf;

char s[210][200010];

struct matrix

{

long long v[210][210];

friend matrix operator * ( matrix m1,matrix m2 )

{

matrix res;

for ( int i=1;i<=n;i++ )

for ( int j=1;j<=n;j++ )

{

res.v[i][j]=inf;

for ( int k=1;k<=n;k++ )

res.v[i][j]=min(res.v[i][j],m1.v[i][k]+m2.v[k][j]);

}

return res;

}

}mtrx;

inline void qp ( int x )

{

for ( ;x;x>>=1,mtrx=mtrx*mtrx )

if ( x&1 )

{

for ( int i=1;i<=n;i++ ) g[i]=inf;

for ( int i=1;i<=n;i++ )

for ( int j=1;j<=n;j++ ) g[j]=min(g[j],f[i]+mtrx.v[i][j]);

for ( int i=1;i<=n;i++ ) f[i]=g[i];

}

}

int main()

{

scanf("%d%d",&n,&m);

for ( int i=1;i<=n;i++ ) scanf(" %s",s[i]+1),l[i]=f[i]=strlen(s[i]+1);

for ( int i=1;i<=n;i++ )

for ( int j=1;j<=n;j++ )

{

mtrx.v[i][j]=l[j];

unsigned long long hsh1=0,hsh2=0,p=1;

if ( i==j ) continue;

for ( int k=1;k<=min(l[i],l[j]);k++ )

{

hsh1+=p*s[i][l[i]-k+1],hsh2=hsh2*P+s[j][k],p*=P;

if ( hsh1==hsh2 ) mtrx.v[i][j]=l[j]-k;

}

}

qp(m-1);

for ( int i=1;i<=n;i++ ) ans=min(ans,f[i]);

return !printf("%lld",ans);

}

cpp

运行