题意：给出几个基因片段，要求你将它们排列成一个最短的序列，序列中使用了所有的基因片段，而且不能翻转基因。
分析：先计算出add数组，再dfs枚举。
空间复杂度O(n*n), 最坏时间复杂度 O(n^n)，但是剪枝以后很快，因为好多搜不到后面，搜不到第n层。
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cstdio>
#include <vector>
#include <algorithm>
#define LL long long
using namespace std;
const int maxn = +;
const int INF = <<;
int n, len[maxn], add[maxn][maxn], ans;
bool vis[maxn];
char s[maxn][maxn]; void cal(int a, int b, int lena, int lenb) //add计算串a在串b，前面增加的字符个数。
{
int i, j, k, f, x;
for(i = ; i < lena; i++)
{
f = ;
for(j = , k = i; j < lenb && k < lena; j++, k++)
{
if(s[a][k] == s[b][j]) continue;
else { f = ; break; }
}
if(f == ) break;
}
x = lena - i;
add[a][b] = lenb - x;
if(add[a][b]<) add[a][b] = ;
}
void dfs(int pre, int sum, int lenth) //分别代表之前的串，和串的总数，总串的长度。
{
if(lenth >= ans) return;
if(sum == n)
{
if(lenth < ans) ans = lenth;
return;
}
for(int i = ; i < n; i++)
{
if(!vis[i])
{
vis[i] = true;
if(add[pre][i]==) //一定要注意这是存在包含串，如abcdabc 包含 dab
//串a包含串b，等价于从a到b的边等于0，那么这时，状态在转移时，在原本
//是以串a结尾的状态加入串b，此时目标状态仍然是以串a结尾，这里需要注意。
dfs(pre, sum+, lenth+add[pre][i]);
else
dfs(i, sum+, lenth+add[pre][i]);
vis[i] = false;
}
}
}
int main()
{
int t, i, j;
scanf("%d", &t);
while(t--)
{
ans = INF;
memset(add, , sizeof(add));
memset(vis, false, sizeof(vis));
scanf("%d", &n);
for(i = ; i < n; i++)
{
scanf("%s", s[i]);
len[i] = strlen(s[i]);
}
for(i = ; i < n; i++)
for(j = ; j < n; j++)
cal(i, j, len[i], len[j]);
for(i = ; i < n; i++)
{
vis[i] = true;
dfs(i, , len[i]);
vis[i] = false;
}
printf("%d\n", ans);
}
return ;
}