思路：好像以前谁问过我这题。。。 状个压就好啦， 把包含在其他串中的字符串删掉， 预处理除每两个字符串之间的关系，
dp[ state ][ i ] 表示在state的状态下， 最后一个字符串是第i个的最优解， 字典序最小的话暴力把转移过程中的字符串存下来
就好啦。
#include<bits/stdc++.h>
#define LL long long
#define fi first
#define se second
#define mk make_pair
#define pii pair<int,int>
#define piii pair<int, pair<int,int>> using namespace std; const int N=+;
const int M=1e4+;
const int inf=0x3f3f3f3f;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int mod=1e9 + ; int n, top, up, cost[][], len[], ret[], dp1[ << ][];
string s[], t[], dp2[ << ][]; int cal(string &a, string &b, int len1, int len2) {
for(int i = max(, len2 - len1); i < len2; i++) {
bool flag = true;
for(int j = i, k = ; j < len2; j++, k++) {
if(b[j] != a[k]) {
flag = false;
break;
}
}
if(flag) {
return len1 - (len2 - i);
}
}
return len1;
} bool check(string &t) {
for(int i = ; i < top; i++) {
for(int j = ; j < s[i].size(); j++) {
string ret = s[i].substr(j, t.size());
if(ret == t) return false;
}
}
return true;
} bool cmp(const string &a, const string &b) {
return a.size() > b.size();
}
int main() {
memset(dp1, inf, sizeof(dp1));
scanf("%d", &n);
for(int i = ; i < n; i++) {
cin >> t[i];
} sort(t, t + n, cmp); for(int i = ; i < n; i++) {
if(check(t[i])) {
s[top++] = t[i];
}
} n = top; up = << n; for(int i = ; i < n; i++)
len[i] = s[i].size(); for(int i = ; i < n; i++) {
for(int j = ; j < n; j++) {
if(i == j) continue;
cost[i][j] = cal(s[i], s[j], len[i], len[j]);
}
} for(int i = ; i < n; i++) {
dp1[ << i][i] = len[i];
dp2[ << i][i] = s[i];
} for(int state = ; state < up; state++) {
for(int i = ; i < n; i++) {
if(dp1[state][i] == inf)
continue;
for(int j = ; j < n; j++) {
if((state >> j) & ) continue;
if(dp1[state ^ ( << j)][j] > dp1[state][i] + cost[j][i]) {
dp1[state ^ ( << j)][j] = dp1[state][i] + cost[j][i];
dp2[state ^ ( << j)][j] = dp2[state][i] + s[j].substr(len[j] - cost[j][i], cost[j][i]);
} else if(dp1[state ^ ( << j)][j] == dp1[state][i] + cost[j][i]) {
string ret = dp2[state][i] + s[j].substr(len[j] - cost[j][i], cost[j][i]);
if(ret < dp2[state ^ ( << j)][j])
dp2[state ^ ( << j)][j] = dp2[state][i] + s[j].substr(len[j] - cost[j][i], cost[j][i]);
}
}
}
} int id = ; for(int i = ; i < n; i++) {
if(dp1[up - ][i] < dp1[up - ][id]) {
id = i;
} else if(dp1[up - ][i] == dp1[up - ][id] && dp2[up - ][i] < dp2[up - ][id]) {
id = i;
}
} cout << dp2[up - ][id] << endl;
return ;
}
/*
*/