BZOJ1195 HNOI2006最短母串(状压dp)

  按照子串出现的先后考虑。令f[i][j]为已经出现的字符串集合为i,最后一个出现的字符串为j时的最短串长,预处理一下任意两个串的最长重叠长度,转移显然。有点麻烦的是字典序,强行增加代码难度。

  另一个比较简单的做法是上AC自动机,建出来后类似地令f[i][j]为已经出现的字符串集合为i,在自动机上点j时的最短串长,相当于跑一个最短路,bfs时每次优先选字典序最小的边即可。

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
#define N 12
#define M 52
int n,len[N],d[N][N];
char s[N][M];
struct str
{
int n;char s[N*M];
bool operator <(const str&a) const
{
for (int i=;i<=n;i++)
if (s[i]!=a.s[i]) return s[i]<a.s[i];
return ;
}
};
str get(int p,int q);
struct data
{
int i,j,x,n,s[N+];
bool operator <(const data&a) const
{
if (x!=a.x) return x<a.x;
return get(i,j)<get(a.i,a.j);
}
}f[<<N][N];
str get(int p,int q)
{
int n=f[p][q].n;
str v;memset(v.s,,sizeof(v.s));
int x=len[f[p][q].s[]];
for (int i=;i<=len[f[p][q].s[]];i++) v.s[i]=s[f[p][q].s[]][i];
for (int i=;i<=n;i++)
for (int j=d[f[p][q].s[i-]][f[p][q].s[i]]+;j<=len[f[p][q].s[i]];j++)
v.s[++x]=s[f[p][q].s[i]][j];
v.n=x;
return v;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("bzoj1195.in","r",stdin);
freopen("bzoj1195.out","w",stdout);
const char LL[]="%I64d\n";
#else
const char LL[]="%lld\n";
#endif
n=read();
for (int i=;i<n;i++) scanf("%s",s[i]+),len[i]=strlen(s[i]+);
for (int i=;i<n;i++)
for (int j=;j<n;j++)
if (i!=j)
for (int k=;k<=len[i];k++)
{
bool flag=;
for (int x=;x<=len[j]&&k+x-<=len[i];x++)
if (s[i][k+x-]!=s[j][x]) {flag=;break;}
if (flag) {d[i][j]=min(len[i]-k+,len[j]);break;}
}
for (int i=;i<(<<n);i++)
for (int j=;j<n;j++)
f[i][j].x=,f[i][j].i=i,f[i][j].j=j;
for (int i=;i<n;i++) f[<<i][i].x=len[i],f[<<i][i].s[]=i,f[<<i][i].n=;
for (int i=;i<(<<n);i++)
for (int j=;j<n;j++)
if (i&(<<j))
for (int k=;k<n;k++)
if (!(i&(<<k)))
if (d[j][k]==len[k]) f[i|(<<k)][j]=min(f[i|(<<k)][j],f[i][j]),f[i|(<<k)][j].i=i|(<<k);
else
{
data t=f[i][j];
f[i][j].x+=len[k]-d[j][k];
f[i][j].s[++f[i][j].n]=k;
f[i|(<<k)][k]=min(f[i|(<<k)][k],f[i][j]),f[i|(<<k)][k].i=i|(<<k),f[i|(<<k)][k].j=k;
f[i][j]=t;
}
for (int i=;i<n;i++) f[(<<n)-][]=min(f[(<<n)-][],f[(<<n)-][i]),f[(<<n)-][].j=;
printf("%s",get((<<n)-,).s+);
return ;
}
上一篇:从一条巨慢SQL看基于Oracle的SQL优化(重磅彩蛋+PPT)


下一篇:【转】使用SQL Tuning Advisor STA优化SQL