1195: [HNOI2006]最短母串
Time Limit: 10 Sec Memory Limit: 32 MBSubmit: 894 Solved: 288[Submit][Status][Discuss]
Description
给定n个字符串（S1,S2,„,Sn），要求找到一个最短的字符串T，使得这n个字符串（S1,S2,„,Sn）都是T的子串。
Input
第一行是一个正整数n（n<=12），表示给定的字符串的个数。以下的n行，每行有一个全由大写字母组成的字符串。每个字符串的长度不超过50.
Output
只有一行，为找到的最短的字符串T。在保证最短的前提下，如果有多个字符串都满足要求，那么必须输出按字典序排列的第一个。
Sample Input
2 ABCD BCDABC
Sample Output
ABCDABC
本来高高兴兴写了个DP，然而发现根本无法解决字典序问题，怎么办能？
搜吧。。。。。
我们假设已经正确地写出了DP，从而得出了答案的长度以及一个字典序不怎么优的解，我们还是dfs枚举顺序，保证当前枚举字符串的字典序小于答案。
一个强剪枝：如果当前所有没有选的串的“最少选择增加量”之和加上当前字符串长度大于答案直接break
然后就过了。。。。
maya，以后这类DP题我都会做了！
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<
string>
#include<vector>
#include<cassert>
using namespace std;
#define MAXN 13
#define MAXS 55
#define INF 0x3f3f3f3f
char str[
20][
55];
string res;
int bstans=
INF;
namespace task1
{
string str[MAXN];
char ss[MAXN][MAXS];
int len[MAXN];
int dis[MAXN][MAXN];
int dp[MAXN][
1<<
13];
int rec[MAXN][
1<<
13][
2];
char res[MAXN*
MAXS];
void deal(
int &x,
int y)
{
if (x>y)x=
y;
}
bool cmp_str(
const string& s1,
const string &
s2)
{
for (
int i=
1;i<=min(s1.length(),s2.length());i++
)
{
if (s1[s1.length()-i]!=s2[s2.length()-i])
return s1[s1.length()-i]<s2[s2.length()-
i];
}
return false;
}
int main(
int n)
{
int m,i,j,k1,k2,k;
int x,y;
for (i=
0;i<n;i++
)
{
str[i]=
::str[i];
}
for (j=
0;j<n;j++
)
for (i=
0;i<n;i++
)
if (i!=j && str[i].find(str[j])!=-
1)
{
swap(str[n-
1],str[j]);
str[--n]=
"";
j--
;
break;
}
sort(str,&
str[n],cmp_str);
for (i=
0;i<n;i++
)
len[i]=
str[i].length(),strcpy(ss[i],str[i].c_str());
// memset(dis,INF,sizeof(dis));
for (i=
0;i<n;i++
)
{
for (j=
0;j<n;j++
)
{
if (i==j)
continue;
dis[i][j]=
len[j];
for (k1=
0;k1<len[i];k1++
)
{
bool flag=
true;
for (k2=
0;k2+k1<len[i] && k2<len[j];k2++
)
{
if (ss[i][k1+k2]!=
ss[j][k2])
{
flag=
false;
break;
}
}
if (flag)
{
dis[i][j]=max(
0,-(len[i]-k1)+
len[j]);
break;
}
}
}
}
memset(dp,INF,sizeof(dp));
for (i=
0;i<n;i++
)
dp[i][1<<i]=
len[i];
int ii;
for (ii=
0;ii<n;ii++
)
{
for (k=
0;k<n;k++
)
{
for (j=
0;j<(
1<<n);j++
)
{
if (__builtin_popcount(j)!=ii)
continue;
for (i=
0;i<n;i++
)
{
if (dp[i][j]==INF)
continue;
if ((j&(
1<<k))==
0)
{
if (dp[k][j|(
1<<k)]>dp[i][j]+
dis[i][k])
{
dp[k][j|(
1<<k)]=dp[i][j]+
dis[i][k];
rec[k][j|(
1<<k)][
0]=
i;
rec[k][j|(
1<<k)][
1]=
j;
}
}
}
}
}
}
int ans=
INF;
for (i=
0;i<n;i++
)
if (ans>dp[i][(
1<<n)-
1])
{
ans=dp[i][(
1<<n)-
1];
x=
i;
y=(
1<<n)-
1;
}
vector<
int>
vec;
int xx,yy;
for (i=
0;i<n;i++
)
{
vec.push_back(x);
xx=x;yy=
y;
x=rec[xx][yy][
0];
y=rec[xx][yy][
1];
}
for (
int i=
0;i<vec.size()/
2;i++
)
swap(vec[i],vec[vec.size()-
1-
i]);
strcat(res,ss[vec[0]]);
for (i=
1;i<vec.size();i++
)
{
strcat(res,ss[vec[i]]+len[vec[i]]-dis[vec[i-
1]][vec[i]]);
}
::res=
res;
::bstans=
ans;
}
}
int cst[
20][
20];
int len[
20];
bool bad[
20];
string curs;
int cnt;
int n;
bool cmp_pair(pair<
char*,
int> p1,pair<
char*,
int>
p2)
{
return strcmp(p1.first,p2.first)<
0;
}
int mncst[
22];
int dfs(
int now,
int status,
int tdis,
int cnt)
{
if (tdis>bstans)
return 0;
if (curs>res)
return 0;
int t=
0,ret=
1;
for (
int i=
0;i<n;i++
)
{
if (!(status&(
1<<
i)))
{
t+=
mncst[i];
}
}
if (t+tdis>
bstans)
return 0;
if (status==(
1<<n)-
1)
{
if (bstans>
tdis)
{
assert(false);
res=
curs;
bstans=
tdis;
}else
{
res=min(res,
string(curs));
}
return 1;
}
pair<
char *,
int> seq[
13];
int tots=
0;
for (
int i=
0;i<n;i++
)
if (!(status&(
1<<
i)))
seq[tots++]=make_pair(str[i] + len[i]-
cst[now][i],i);
sort(seq,seq+
tots,cmp_pair);
for (
int i=
0;i<tots;i++
)
{
curs+=str[seq[i].second]+(len[seq[i].second]-
cst[now][seq[i].second]);
t=dfs(seq[i].second,status|(
1<<seq[i].second),tdis+cst[now][seq[i].second],cnt*
2/
tots);
cnt-=
t;
ret+=
t;
curs=curs.substr(
0,tdis);
//if (cnt<=0)break;
}
return ret;
}
int main()
{
// freopen("input.txt","r",stdin);
int x,y,z;
scanf("%d",&
n);
for (
int i=
0;i<n;i++
)
{
scanf("%s",str[i]);
len[i]=
strlen(str[i]);
}
task1::main(n);
for (
int i=
0;i<n;i++
)
{
if (bad[i])
continue;
for (
int j=
0;j<n;j++
)
{
if (i==j)
continue;
for (
int k=
0;k<len[i];k++
)
{
bool flag2=
false;
for (
int k2=
0;k+k2<len[i];k2++
)
{
if (str[i][k2+k]!=
str[j][k2])
{
break;
}
if (k2==len[j]-
1)
{
flag2=
true;
break;
}
}
if (flag2)
bad[j]=
true;
}
}
}
x=
0;
for (
int i=
0;i<n;i++
)
{
if (!
bad[i])
strcpy(str[x++
],str[i]);
}
n=
x;
char tmp[
55];
for (
int i=
0;i<n;i++
)
for (
int j=i;j<n;j++
)
if (
string(str[i])>
string(str[j]))
{
strcpy(tmp,str[i]);
strcpy(str[i],str[j]);
strcpy(str[j],tmp);
}
for (
int i=
0;i<n;i++
)
len[i]=
strlen(str[i]);
for (
int i=
0;i<n;i++
)
{
for (
int j=
0;j<n;j++
)
{
if (i==j)
continue;
for (
int k=
0;k<=len[i];k++
)
{
bool flag=
true;
for (
int k2=
0;k2+k<len[i];k2++
)
{
if (str[i][k2+k]!=
str[j][k2])
{
flag=
false;
break;
}
}
if (flag)
{
cst[i][j]=len[j]-(len[i]-
k);
break;
}
}
}
}
for (
int i=
0;i<n;i++
)
{
int x=
INF;
for (
int j=
0;j<n;j++
)
{
if (i==j)
continue;
x=
min(x,cst[j][i]);
}
mncst[i]=
x;
}
for (
int i=
0;i<n;i++
)
{
curs=
str[i];
dfs(i,1<<i,len[i],
100000000);
}
cout<<res<<
endl;
}
转载于:https://www.cnblogs.com/mhy12345/p/4513278.html
