BZOJ 2085 Poi2010 Hamsters Hash+倍增Floyd
來(lái)源：程序員人生 發(fā)布時(shí)間：2015-04-02 08:17:46 閱讀次數(shù)：3626次
題目大意：給定n個(gè)長(zhǎng)度總和不超過(guò)10W的字符串，求1個(gè)最短的母串，使所有字符串的出現(xiàn)次數(shù)之和=m 這n個(gè)字符串保證不相互包括
TM能不能好好翻譯了
令f[i][j]表示第i個(gè)字符串后面接上第j個(gè)字符串后會(huì)增加多少長(zhǎng)度
由于j1定不是i的子串，因此這實(shí)際上就是在求i的最長(zhǎng)的后綴，該后綴同時(shí)也是j的前綴
注意不能連出長(zhǎng)度為0的邊，因此當(dāng)i=j時(shí)要保證這個(gè)長(zhǎng)度<len[i]
怎樣求呢？其實(shí)Hash1下，枚舉i和j，暴力做就能夠了
這不會(huì)T？
首先設(shè)第i個(gè)字符串的長(zhǎng)度為ai，設(shè)k=Σai
易知當(dāng)計(jì)算f[i][j]時(shí)的復(fù)雜度是O(min(ai,aj))
那末現(xiàn)在的問(wèn)題就是當(dāng)k固定時(shí)，最大化ΣΣmin(ai,aj)
我們將所有的ai排個(gè)序，容易發(fā)現(xiàn)當(dāng)相鄰的兩個(gè)數(shù)ai和aj都變成(ai+aj)/2時(shí)目標(biāo)函數(shù)1定會(huì)增大
證明：
若ak<=ai<aj，那末min(ak,ai)和min(ak,aj)都不變
若ai<aj<=ak，那末min(ai,ak)+min(aj,ak)=ai+aj1定不變
min(ai,ai)+min(aj,aj)=ai+aj也不變
只有min(ai,aj)增大了
因此終究當(dāng)所有的ai都相同時(shí)目標(biāo)函數(shù)最大
故每一個(gè)ai都等于k/n，這1步的終究時(shí)間復(fù)雜度是O(k/n*n^2)=O(kn)
k=10W，n=200，明顯不會(huì)T
現(xiàn)在的問(wèn)題就是給定1張圖求源點(diǎn)動(dòng)身走m條邊的最短路
倍增Floyd便可
終究時(shí)間復(fù)雜度O(kn+n^3logn)
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define M 220
#define BASE 131
#define MOD 999911657
using namespace std;
int n,m,len[M];
char str[101000],*s[M];
long long power[101000],_hash[101000],*hash[M];
long long f[M][M],g[M][M],ans[M][M];
int Get_Hash(long long *hash,int l,int r)
{
int len=r-l+1;
return (hash[r]-hash[l⑴]*power[len]%MOD+MOD)%MOD;
}
int Calculate(int x,int y)//計(jì)算x最長(zhǎng)的后綴，這個(gè)后綴也是y的前綴
{
int i;
for(i=min(len[x],len[y])-(len[y]<=len[x]);~i;i--)
if( Get_Hash(hash[x],len[x]-i,len[x]⑴) == Get_Hash(hash
[y],0,i⑴) )
return i;
return 0;
}
int main()
{
int T,i,j,k;
cin>>n>>m;
int temp=1,max_len=0;
for(i=1;i<=n;i++)
{
scanf("%s",str+temp);
s[i]=str+temp;
hash[i]=_hash+temp;
len[i]=strlen(s[i]);
max_len=max(max_len,len[i]);
++temp+=len[i];
for(j=0;j<len[i];j++)
hash[i][j]=(hash[i][j⑴]*BASE+s[i][j])%MOD;
}
for(power[0]=1,i=1;i<=max_len;i++)
power[i]=power[i⑴]*BASE%MOD;
memset(f,0x3f,sizeof f);
for(i=1;i<=n;i++)
{
f[0][i]=len[i];
for(j=1;j<=n;j++)
f[i][j]=len[j]-Calculate(i,j);
}
memset(ans,0x3f,sizeof ans);
for(i=1;i<=n;i++)
ans[i][i]=0;
for(T=0;(1<<T)<=m;T++)
{
if(T)
{
memset(g,0x3f,sizeof g);
for(k=0;k<=n;k++)
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
g[i][j]=min(g[i][j],f[i][k]+f
[k][j]);
memcpy(f,g,sizeof f);
}
if(m&(1<<T) )
{
memset(g,0x3f,sizeof g);
for(k=0;k<=n;k++)
for(i=0;i<=n;i++)
for(j=0;j<=n;j++)
g[i][j]=min(g[i][j],f[i][k]
+ans[k][j]);
memcpy(ans,g,sizeof ans);
}
}
long long ans=0x3f3f3f3f3f3f3f3fll;
for(i=1;i<=n;i++)
ans=min(ans,::ans[0][i]);
cout<<ans<<endl;
return 0;
}
生活不易，碼農(nóng)辛苦
如果您覺(jué)得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
