BZOJ2085 [Poi2010]Hamsters

题面

给出 $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;
}
暂无评论

发送评论 编辑评论


|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇