#include<stdlib.h>
#include<string.h>
int n,i,j,k,l,m,t,t1,t2,t3,t4,i1,j1,fla,c[18][18],sz[18],a[18],b[60],d[16][25000],d2[16][25000],e[18],ma;
int x,x1,x2,x3,x4;
int max(int a,int b){
int t;
if (a>b) t=a; else t=b;
return t;
}
int min(int a,int b){
int t;
if (a<b) t=a; else t=b;
return t;
}
char ch[18][95],cht;
int main(){
scanf("%d",&n);
sz[1]=1;
for (i=2;i<=16;i++)
sz[i]=sz[i-1]*2;
for (i=1;i<=n;i++){
scanf("%s",ch[i]);
a[i]=0;
}
for (i=1;i<=n;i++){
for (j=i+1;j<=n;j++){
t1=0;
while (ch[i][t1]==ch[j][t1]&&ch[i][t1]!='\0'&&ch[j][t1]!='\0')
t1++;
if (ch[i][t1]>ch[j][t1]||ch[j][t1]=='\0'){
for (k=0;k<=54;k++){
cht=ch[i][k];ch[i][k]=ch[j][k];ch[j][k]=cht;
}
}
}}
for (i=1;i<=n;i++){
for (j=1;j<=n;j++){
if (i!=j){
t1=strlen(ch[i]);t2=strlen(ch[j]);t3=0;ma=0;
for (k=t2-1;k>=0&&a[i]==0;k--){
for (l=1;l<=t3;l++){
if (b[l]!=0&&ch[j][k]==ch[i][t1-b[l]-1]) {b[l]++;if (b[l]==t1) a[i]=1;} else b[l]=0;
}
if (ch[j][k]==ch[i][t1-1]){
t3++;b[t3]=1;//ma=max(ma,1);
}
}
for (k=1;k<=t3;k++)
ma=max(ma,b[k]);
c[i][j]=ma;
}}}
m=0;
for (i=1;i<=n;i++){
if (a[i]==0){m++;b[m]=i;}
}
for (i=1;i<=m;i++){
for (j=1;j<=5000;j++)
d[i][j]=99999999;
}
for (i=1;i<=m;i++){
t1=sz[i];
d[i][t1]=strlen(ch[b[i]]);
}
for (i1=2;i1<=m;i1++){
for (j1=1;j1<=m;j1++){
for (k=0;k<=i1;k++)
e[k]=k;
if (i1>=j1) fla=1; else fla=0;
while (e[0]==0){
while (e[0]==0&&fla==0){
j=i1;
while (e[j]==m-i1+j&&j>0){
j--;
// printf("%d\n",j);
}
e[j]++;
for (i=j+1;i<=i1;i++)
e[i]=e[i-1]+1;
fla=0;
for (i=1;i<=i1;i++)
if (e[i]==j1) fla=1;
}
if (e[0]==0){
t1=0;
for (j=1;j<=i1;j++){
t1+=sz[e[j]];
}
for (j=1;j<=i1;j++){
if (e[j]!=j1){
t2=sz[e[j]];
t3=d[e[j]][t1-sz[j1]]+strlen(ch[b[j1]])-c[b[j1]][b[e[j]]];
if (t3<=d[j1][t1]) {
if (t3==d[j1][t1]){
x1=d2[j1][t1];x2=e[j];
x3=c[b[j1]][b[x1]];
x4=c[b[j1]][b[x2]];
while (ch[x1][x3]==ch[x2][x4]){
x3++;x4++;
}
if (ch[x1][x3]>ch[x2][x4]) t4=1; else t4=0;
} else t4=1;
if (t4==1){d[j1][t1]=t3;d2[j1][t1]=e[j];}}
}}
fla=0;
}}
}}
t1=sz[m+1]-1;t2=99999999;t3=0;
for (i=1;i<=m;i++){
if (d[i][t1]<t2){t2=d[i][t1];t3=i;}
}
for (i=0;ch[t3][i]!='\0';i++){
printf("%c",ch[t3][i]);
}
for (i=2;i<=m;i++){
t4=d2[t3][t1];
x1=c[b[t3]][b[t4]];
for (j=x1;ch[b[t4]][j]!='\0';j++)
printf("%c",ch[b[t4]][j]);
t1-=sz[t3];
t3=t4;
}
printf("\n");
//printf("%d\n",t2);
//system("pause");
}
点7Wa,,,点8无输出,其它都A,
点7
测试结果错误.错误结果为:BAAABABAABBAAABBBABABAABAABABBBBABBBAABBABABBABBBAAABABAABBAABBBBABABBAABABABBBBBBBBABAAABABAAAAABBAABAAABAABBBBBABBBBBAABBBBABBBBBBABAAAAABAABBBBBABBAABAABBAAABABBBAAABBBBBABAABAAAAABBBBBABABABBAAABABABBBBABAABABBBABABABBBAAABBABBBABAABBBAAABABBABBBAAAABBBBAAAAABBBBABBBBABBAABAAABAAABBBABBBBBAAAAABABBBAAABBABBAABABAABAAABAAA
正确结果应为:BAABAAABABBBBBABBBABAAAAAABBAAABBBAAABABBBABBBABABAABAABABBBBABBBAABBABABBABBBAAABABAABBAABAAABAABBBBBABBBBBAABBBBABBBBBBABAAAAABAABBBBBABBAABAABBAAABABBBAAABBBBBABAABAAAAABBBBBABABABBAAABABABBAABBBBABABBAABABABBBBBBBBABAAABABAAAAABBBBABAABABBBABABABBBAAABBABBBABAABBBAAABABBABBBAAAABBBBAAAAABBBBABBBBABBAABAAABAAABBBABBBBBAAAAABABBBAAABBABBAABABAABAAABAAA
点8:输出过少|用户输出数据少于标准输出的50%[标准输出50位|选手输出0位]
求神牛看看,谢谢了!