题意：
给n个由A C T G组成的字符串。
要求用这些字符串拼接，（如果两个穿的前缀和后缀有相同的部分可以重合），要求拼接成的串
长度最短且字典序最小。
一直觉得是什么“字符串不会做系列”的难题，结果是一道状压DP+dfs
看到n=15这么灵性的数字应该要灵性一下的。。。
二进制状压一下
dp[state][j] 表示在state状态下，最前面的串是j的情况
然后需要预处理一下两个串拼接的时候增加的长度
dist[i][j] 表示把第i个串拼在第j个串前面增加的长度：也就是i串的长度减去i的后缀和j的前缀重合的长度
对于dfs回溯
在得到短长度，并且字典序在当前最小时，最前面的串j时，需要找第二个串，已经知道dp[all-state[j]][j]
那么枚举转移过来的情况 找到满足dp值满足，并且拼接后字典序最小的（注意这里是要去拼接比较一下，因为直接比较可能把前缀就隐藏了，不是直接比较下一个串的字典序）
易错，还有一点在输入串后，要办能够直接有完全重合的串处理掉。
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 #include <queue> 5 #include <vector> 6 #include <algorithm> 7 #include <stack> 8 #include <set> 9 #include <map> 10 #include <math.h> 11 #define pb push_back 12 #define CLR(a) memset(a, 0, sizeof(a)); 13 #define MEM(a, b) memset(a, b, sizeof(a)); 14 #define fi first 15 #define se second 16 17 using namespace std; 18 19 typedef long long ll; 20 21 const int MAXN = 107; 22 const int MAXV = 207; 23 const int MAXE = 207; 24 const int INF = 0x3f3f3f3f; 25 26 int sz; 27 char s[MAXN << 1][MAXN]; 28 char str[MAXN << 1][MAXN]; 29 int n; 30 int state[27]; 31 int dp[67000 << 1][27]; 32 int dist[27][27]; 33 char anstr[MAXN*MAXN << 1]; 34 void deal() 35 { 36 for (int i = 0; i < sz; i++) 37 { 38 for (int j = 0; j < sz; j++) 39 { 40 if (i == j) continue; 41 int len = min(strlen(s[i]), strlen(s[j])); 42 for (int l = len; l >= 0; l--) 43 { 44 char ss[MAXN]; 45 strcpy(ss, s[j]); 46 ss[l] = ' '; 47 //if (i == 0 && j == 1) cout << l << " : " << s[i]+(strlen(s[i])-l) << " " << ss << endl; 48 if (strcmp(s[i]+(strlen(s[i])-l), ss) == 0) 49 { 50 dist[i][j] = strlen(s[i]) - l; 51 break; 52 } 53 } 54 } 55 } 56 } 57 58 int all; 59 void dfs(int crt, int pre) 60 { 61 if (crt == 0) return; 62 int tmp = INF; 63 int now = -1; 64 char ts1[MAXN*MAXN], ts2[MAXN*MAXN]; 65 bool have = false; 66 strcpy(ts1, anstr); 67 for (int i = 0; i < sz; i++) 68 { 69 if (crt & state[i]) 70 { 71 if (dp[crt+state[pre]][pre] == dp[crt][i] + dist[pre][i]) 72 { 73 if (!have) 74 { 75 now = i; 76 have = 1; 77 int d = strlen(s[pre]) - dist[pre][now]; 78 strcat(ts1, s[now]+d); 79 } 80 else 81 { 82 strcpy(ts2, anstr); 83 int d = strlen(s[pre]) - dist[pre][i]; 84 strcat(ts2, s[i]+d); 85 if (strcmp(ts2, ts1) < 0) 86 { 87 now = i; 88 strcpy(ts1, ts2); 89 } 90 } 91 } 92 } 93 } 94 strcpy(anstr, ts1); 95 dfs(crt - state[now], now); 96 } 97 int main() 98 { 99 state[0] = 1; 100 for (int i = 1; i <= 16; i++) state[i] = state[i-1] << 1; 101 int T; 102 scanf("%d", &T); 103 for (int cas = 1; cas <= T; cas++) 104 { 105 sz = 0; 106 scanf("%d", &n); 107 for (int i = 0; i < n; i++) scanf("%s", str[i]); 108 for (int i = 0; i < n; i++) 109 { 110 bool flag = true; 111 for (int j = 0; j < n; j++) 112 { 113 if (i == j) continue; 114 if (strstr(str[j], str[i])) 115 { 116 flag = false; 117 break; 118 } 119 } 120 if (flag) strcpy(s[sz++], str[i]); 121 } 122 printf("Scenario #%d: ", cas); 123 if (sz == 0) 124 { 125 cout << str[0] << endl << endl; 126 continue; 127 } 128 if (sz == 1) 129 { 130 cout << s[0] << endl << endl; 131 continue; 132 } 133 deal(); 134 all = state[sz] - 1; 135 MEM(dp, 0x3f); 136 for (int i = 0; i < sz; i++) dp[state[i]][i] = strlen(s[i]); 137 for (int i = 0; i <= all; i++) 138 { 139 for (int j = 0; j < sz; j++) 140 { 141 if (dp[i][j] == INF) continue; 142 for (int k = 0; k < sz; k++) 143 { 144 if (state[k] & i) continue; 145 dp[i+state[k]][k] = min(dp[i+state[k]][k], dp[i][j]+dist[k][j]); 146 } 147 } 148 } 149 int ans = INF; 150 int now = -1; 151 for (int i = 0; i < sz; i++) 152 { 153 if (ans > dp[all][i]) 154 { 155 ans = dp[all][i]; 156 strcpy(anstr, s[i]); 157 now = i; 158 } 159 else if (ans == dp[all][i] && strcmp(s[i], anstr) < 0) 160 { 161 strcpy(anstr, s[i]); 162 now = i; 163 } 164 } 165 dfs(all-state[now], now); 166 cout << anstr << endl << endl; 167 } 168 return 0; 169 }