题意分析

给定$N$个DNA子序列（每个长度在$1$到$7$之间，$2 \leq N \leq 7$），需要通过合并操作将它们拼接成一个完整序列。合并规则如下：

1. 重叠部分：必须是一个字符串的末尾与另一个字符串的开头的最长公共部分。例如：
   • $GATTA + TACA$合并为$GATTACA$（重叠部分为$TA$）。
   • $TACA + GATTA$合并为$TACAGATTA$（无重叠）。
2. 目标：找到所有可能的合并顺序中，最终序列长度最短的结果。

解题思路

1. 问题本质：这是一个排列组合问题，需要枚举所有可能的合并顺序，计算每种顺序下的最终序列长度，取最小值。
2. 关键点：
   • 合并顺序影响结果：例如$A+B$和$B+A$可能得到不同长度的序列。
   • 重叠计算：对于任意两个字符串$s_1$和$s_2$，需找到$s_1$的末尾与$s_2$开头的最大重叠长度$k$（$0 \leq k \leq \min(len(s_1), len(s_2))$），合并后的长度为$len(s_1) + len(s_2) - k$。
3. 算法选择：
   • 暴力枚举：由于$N \leq 7$，可以枚举所有排列（$7! = 5040$种可能），对每种排列按顺序合并并记录最短长度。
   • 优化合并：预处理每对字符串之间的最大重叠长度$k$，避免重复计算。
4. 步骤：
   1. 预处理所有字符串两两之间的最大重叠长度$k$。
   2. 生成所有可能的排列（合并顺序）。
   3. 对每种排列，按顺序合并并计算总长度。
   4. 输出所有可能中的最小长度。

标程

#include <iostream>
#include <vector>
#define REP(i, a, b) for(int i = (int)(a); i < (int)(b); ++i)
using namespace std;

vector<string> v(10);
int book[10000], min_len, n;

string merge(string s1, string s2)
{
	int max = 0, index = -1;
	REP(i, 0, s1.length())
	{
		if(s1[i] == s2[0])
		{
			int x = i, y = 0, len = 0;
			while(s1[x++] == s2[y++])
			{
				len++;
				if(x == s1.length() || y == s2.length())
					break;
			}
			if(s1.length() - i == len && len > max)
				max = len, index = i;
		}
	}
	if(index == -1) return s1 + s2;
	else return s1.replace(index, max, s2);
}

void DFS(string s, int now)
{
	if(now == n)
	{
		if(s.length() < min_len)
			min_len = s.length();
		return;
	}
	REP(i, 0, n)
	{
		if(book[i] == 0)
		{
			book[i] = 1;
			DFS(merge(s, v[i]), now + 1);
			book[i] = 0;
		}
	}
}

int main()
{
	string empty;
	while(cin >> n)
	{
		min_len = 999;
		REP(i, 0, n) cin >> v[i];
		DFS(empty, 0);
		cout << min_len << endl;
	}
	return 0;
}