此题似乎是一个dp。。 dp[i][j]表示选了i这个集合的字符串，最后一个是j的最短字符串。 （字典序顺便搞定） 然后发现需要处理掉一串为另一串子串的情况，特判一些特殊情况（或者奇怪的姿势）就好了。。 这题很卡空间，请务必不要乱开数组。
#include <bits/stdc++.h> #define gc getchar() using namespace std; int n,len[13],Len[13]; int length[4096][13],same[13][13],m,pd[13]; char a[13][51],b[13][51],dp[4096][13][601],Now[601],Ans[601]; int read() { int x=1; char ch; while (ch=gc,ch<'0'&&ch>'9') if (ch=='-') x=-1; int s=ch-'0'; while (ch=gc,ch<='9'&&ch>='0') s=s*10+ch-'0'; return s*x; } int main() { n=read(); for (int i=1;i<=n;i++) scanf("%s",a[i]+1),len[i]=strlen(a[i]+1); for (int i=1;i<=n;i++) { bool flag=1; for (int j=1;j<=n&&flag;j++) if (!pd[j]&&len[i]<=len[j]&&i!=j) { for (int k=1;k<=len[j]-len[i]+1;k++) { bool f=1; for (int l=k;l<=k+len[i]-1;l++) if (a[i][l-k+1]!=a[j][l]) { f=0; break; } if (f) { flag=0; break; } } } if (flag) { ++m; for (int j=1;j<=len[i];j++) b[m][j]=a[i][j]; Len[m]=len[i]; } else pd[i]=1; } memset(length,0x3f3f3f,sizeof(length)); for (int i=1;i<=m;i++) { length[1<<(i-1)][i]=Len[i]; for (int j=1;j<=Len[i];j++) dp[1<<(i-1)][i][j]=b[i][j]; } for (int i=1;i<=m;i++) for (int j=1;j<=m;j++) { if (i==j) continue; for (int k=max(1,Len[j]-Len[i]+2);k<=Len[j];k++) { bool flag=1; for (int p=k;p<=Len[j];p++) if (b[i][p-k+1]!=b[j][p]) { flag=0; break; } if (flag) { same[i][j]=Len[j]-k+1; break; } } } for (int last=1;last<(1<<m);last++) for (int i=1;i<=m;i++) if (!(last&(1<<(i-1)))) for (int j=1;j<=m;j++) if (last&(1<<(j-1))) { int now=last^(1<<(i-1)); for (int k=1;k<=length[last][j];k++) Now[k]=dp[last][j][k]; for (int k=same[i][j]+1;k<=Len[i];k++) Now[k+length[last][j]-same[i][j]]=b[i][k]; if (length[last][j]+Len[i]-same[i][j]==length[now][i]) { int k=1; while (dp[now][i][k]==Now[k]) k++; if (k==length[now][i]) continue; if (dp[now][i][k]>Now[k]) for (int p=1;p<=length[now][i];p++) dp[now][i][p]=Now[p]; } if (length[last][j]+Len[i]-same[i][j]<length[now][i]) { length[now][i]=length[last][j]+Len[i]-same[i][j]; for (int k=1;k<=length[now][i];k++) dp[now][i][k]=Now[k]; } } int min_length=601; for (int i=1;i<=m;i++) { if (length[(1<<m)-1][i]==min_length) { int k=1; while (dp[(1<<m)-1][i][k]==Ans[k]) k++; if (dp[(1<<m)-1][i][k]<Ans[k]) for (int j=1;j<=min_length;j++) Ans[j]=dp[(1<<m)-1][i][j]; } if (length[(1<<m)-1][i]<min_length) { min_length=length[(1<<m)-1][i]; for (int j=1;j<=min_length;j++) Ans[j]=dp[(1<<m)-1][i][j]; } } for (int i=1;i<=min_length;i++) putchar(Ans[i]); puts(""); return 0; }