题意：给出几个基因片段，要求你将它们排列成一个最短的序列，序列中使用了所有的基因片段，而且不能翻转基因。
分析：先计算出add数组，再dfs枚举。
空间复杂度O(n*n), 最坏时间复杂度 O(n^n)，但是剪枝以后很快，因为好多搜不到后面，搜不到第n层。
1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cmath> 5 #include <cstdio> 6 #include <vector> 7 #include <algorithm> 8 #define LL long long 9 using namespace std; 10 const int maxn = 20+10; 11 const int INF = 1<<28; 12 int n, len[maxn], add[maxn][maxn], ans; 13 bool vis[maxn]; 14 char s[maxn][maxn]; 15 16 void cal(int a, int b, int lena, int lenb) //add计算串a在串b，前面增加的字符个数。 17 { 18 int i, j, k, f, x; 19 for(i = 0; i < lena; i++) 20 { 21 f = 0; 22 for(j = 0, k = i; j < lenb && k < lena; j++, k++) 23 { 24 if(s[a][k] == s[b][j]) continue; 25 else { f = 1; break; } 26 } 27 if(f == 0) break; 28 } 29 x = lena - i; 30 add[a][b] = lenb - x; 31 if(add[a][b]<0) add[a][b] = 0; 32 } 33 void dfs(int pre, int sum, int lenth) //分别代表之前的串，和串的总数，总串的长度。 34 { 35 if(lenth >= ans) return; 36 if(sum == n) 37 { 38 if(lenth < ans) ans = lenth; 39 return; 40 } 41 for(int i = 0; i < n; i++) 42 { 43 if(!vis[i]) 44 { 45 vis[i] = true; 46 if(add[pre][i]==0) //一定要注意这是存在包含串，如abcdabc 包含 dab 47 //串a包含串b，等价于从a到b的边等于0，那么这时，状态在转移时，在原本 48 //是以串a结尾的状态加入串b，此时目标状态仍然是以串a结尾，这里需要注意。 49 dfs(pre, sum+1, lenth+add[pre][i]); 50 else 51 dfs(i, sum+1, lenth+add[pre][i]); 52 vis[i] = false; 53 } 54 } 55 } 56 int main() 57 { 58 int t, i, j; 59 scanf("%d", &t); 60 while(t--) 61 { 62 ans = INF; 63 memset(add, 0, sizeof(add)); 64 memset(vis, false, sizeof(vis)); 65 scanf("%d", &n); 66 for(i = 0; i < n; i++) 67 { 68 scanf("%s", s[i]); 69 len[i] = strlen(s[i]); 70 } 71 for(i = 0; i < n; i++) 72 for(j = 0; j < n; j++) 73 cal(i, j, len[i], len[j]); 74 for(i = 0; i < n; i++) 75 { 76 vis[i] = true; 77 dfs(i, 1, len[i]); 78 vis[i] = false; 79 } 80 printf("%d ", ans); 81 } 82 return 0; 83 }