思路：好像以前谁问过我这题。。。 状个压就好啦， 把包含在其他串中的字符串删掉， 预处理除每两个字符串之间的关系，
dp[ state ][ i ] 表示在state的状态下， 最后一个字符串是第i个的最优解， 字典序最小的话暴力把转移过程中的字符串存下来
就好啦。
1 #include<bits/stdc++.h> 2 #define LL long long 3 #define fi first 4 #define se second 5 #define mk make_pair 6 #define pii pair<int,int> 7 #define piii pair<int, pair<int,int>> 8 9 using namespace std; 10 11 const int N=100+7; 12 const int M=1e4+7; 13 const int inf=0x3f3f3f3f; 14 const LL INF=0x3f3f3f3f3f3f3f3f; 15 const int mod=1e9 + 7; 16 17 int n, top, up, cost[12][12], len[12], ret[12], dp1[1 << 12][12]; 18 string s[12], t[12], dp2[1 << 12][12]; 19 20 int cal(string &a, string &b, int len1, int len2) { 21 for(int i = max(0, len2 - len1); i < len2; i++) { 22 bool flag = true; 23 for(int j = i, k = 0; j < len2; j++, k++) { 24 if(b[j] != a[k]) { 25 flag = false; 26 break; 27 } 28 } 29 if(flag) { 30 return len1 - (len2 - i); 31 } 32 } 33 return len1; 34 } 35 36 bool check(string &t) { 37 for(int i = 0; i < top; i++) { 38 for(int j = 0; j < s[i].size(); j++) { 39 string ret = s[i].substr(j, t.size()); 40 if(ret == t) return false; 41 } 42 } 43 return true; 44 } 45 46 bool cmp(const string &a, const string &b) { 47 return a.size() > b.size(); 48 } 49 int main() { 50 memset(dp1, inf, sizeof(dp1)); 51 scanf("%d", &n); 52 for(int i = 0; i < n; i++) { 53 cin >> t[i]; 54 } 55 56 sort(t, t + n, cmp); 57 58 for(int i = 0; i < n; i++) { 59 if(check(t[i])) { 60 s[top++] = t[i]; 61 } 62 } 63 64 n = top; up = 1 << n; 65 66 for(int i = 0; i < n; i++) 67 len[i] = s[i].size(); 68 69 for(int i = 0; i < n; i++) { 70 for(int j = 0; j < n; j++) { 71 if(i == j) continue; 72 cost[i][j] = cal(s[i], s[j], len[i], len[j]); 73 } 74 } 75 76 for(int i = 0; i < n; i++) { 77 dp1[1 << i][i] = len[i]; 78 dp2[1 << i][i] = s[i]; 79 } 80 81 for(int state = 1; state < up; state++) { 82 for(int i = 0; i < n; i++) { 83 if(dp1[state][i] == inf) 84 continue; 85 for(int j = 0; j < n; j++) { 86 if((state >> j) & 1) continue; 87 if(dp1[state ^ (1 << j)][j] > dp1[state][i] + cost[j][i]) { 88 dp1[state ^ (1 << j)][j] = dp1[state][i] + cost[j][i]; 89 dp2[state ^ (1 << j)][j] = dp2[state][i] + s[j].substr(len[j] - cost[j][i], cost[j][i]); 90 } else if(dp1[state ^ (1 << j)][j] == dp1[state][i] + cost[j][i]) { 91 string ret = dp2[state][i] + s[j].substr(len[j] - cost[j][i], cost[j][i]); 92 if(ret < dp2[state ^ (1 << j)][j]) 93 dp2[state ^ (1 << j)][j] = dp2[state][i] + s[j].substr(len[j] - cost[j][i], cost[j][i]); 94 } 95 } 96 } 97 } 98 99 int id = 0; 100 101 for(int i = 1; i < n; i++) { 102 if(dp1[up - 1][i] < dp1[up - 1][id]) { 103 id = i; 104 } else if(dp1[up - 1][i] == dp1[up - 1][id] && dp2[up - 1][i] < dp2[up - 1][id]) { 105 id = i; 106 } 107 } 108 109 cout << dp2[up - 1][id] << endl; 110 return 0; 111 } 112 /* 113 */