题意分析

1. 背景是邪恶的弗兰肯斯坦博士想提取、增强并克隆自己的DNA，但在将分解后的DNA短片段拼接回原始序列时遇到困难，于是绑架学生来解决此问题。
2. 问题是给定一个由字符“A”（腺嘌呤）、“C”（胞嘧啶）、“G”（鸟嘌呤）、“T”（胸腺嘧啶）组成的字符串列表，要求找到一个最短的字符串，该字符串要包含给定列表中的所有字符串作为子串。如果存在多个长度最短的字符串，则选择在字母顺序（字典序）上最小的那个。
3. 输入：第一行是测试用例的数量。对于每个测试用例，第一行是字符串的数量(n)（(1 \leq n \leq 15)），接下来(n)行，每行一个长度在(1 \leq length \leq 100)之间的由“A”、“C”、“G”、“T”组成的字符串。
4. 输出：每个测试用例的输出以“Scenario #(i):”开头（(i)从(1)开始），然后输出满足条件的最短且字典序最小的字符串，最后用一个空行结束该测试用例的输出。

解题思路

1. 预处理字符串：首先，对输入的字符串进行处理，去除那些已经是其他字符串子串的字符串，这样可以减少后续处理的复杂度。通过两层循环，使用strstr函数判断一个字符串是否是另一个字符串的子串。
2. 计算字符串间的重叠长度：定义函数Cal，用于计算两个字符串(s1)和(s2)的重叠部分长度。通过遍历(s1)的不同位置，尝试与(s2)进行匹配，找到最长的重叠部分。
3. 初始化动态规划数组和距离矩阵：使用二维数组dis记录每两个字符串之间的重叠长度，使用三维动态规划数组dp，其中dp[i][j]表示状态为(i)（一个二进制数，表示哪些字符串已经被使用）且最后一个使用的字符串是(j)时的最短长度。初始时，对于只使用一个字符串的状态，将其长度赋值给dp数组。
4. 动态规划计算最短长度：通过两层循环遍历所有状态和字符串，对于每个状态和当前未使用的字符串，更新dp数组，计算使用更多字符串时的最短长度。
5. 深度优先搜索找到最短且字典序最小的字符串：通过深度优先搜索（DFS），从最终状态开始，根据dp数组找到最短长度对应的字符串。在搜索过程中，记录下所有可能的字符串，并选择字典序最小的那个作为最终答案。

标程（C++）

#include<cstdio>
#include<cstring>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
const int inf = 1 << 29;  // 定义一个较大的数表示无穷大
const int maxn = 110;  // 字符串的最大长度
const int maxm = 16;  // 字符串的最大数量

// 定义字符串结构体
struct String
{
    char str[maxn];  // 存储字符串
    int len;  // 字符串长度
    bool operator < (const String &a)const
    {
        return strcmp(str, a.str) < 0;  // 重载小于运算符，用于字符串排序
    }
}str[maxm];

int n, ansl, dis[maxm][maxm], dp[1 << maxm][maxn];  // n为字符串数量，ansl为最短长度，dis为字符串间重叠长度矩阵，dp为动态规划数组
string ans;  // 存储最终答案字符串
bool vis[maxm];  // 标记字符串是否已被使用

// 计算两个字符串的重叠长度
int Cal(int s1, int s2)
{
    int lena = str[s1].len;
    int lenb = str[s2].len;
    for (int i = max((int)(lena - lenb), 0); i <= lena; i++)
    {
        bool is = true;
        for (int j = i, k = 0; j < lena; k++, j++)
            if (str[s1].str[j] != str[s2].str[k])
            {
                is = false;
                break;
            }
        if (is)
            return lena - i;
    }
    return 0;
}

// 初始化距离矩阵和动态规划数组
void Init()
{
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (i != j)
                dis[i][j] = Cal(i, j);
    for (int i = 0; i < (1 << n); i++)
        for (int j = 0; j < n; j++)
            dp[i][j] = inf;
    for (int i = 0; i < n; i++)
        dp[1 << i][i] = str[i].len;
}

// 深度优先搜索
void DFS(int cnt, int now, string s, int last)
{
    if (cnt == n)
    {
        if (ans == "" || ans > s)
            ans = s;
        return;
    }
    int id = -1;
    string ss;
    for (int i = 0; i < n; i++)
    {
        if (!vis[i] && dp[now][last] == dp[now ^ (1 << last)][i] + str[last].len - dis[last][i])
        {
            string s1 = s;
            for (int j = dis[last][i]; j < str[i].len; j++)
                s1 += str[i].str[j];
            if (id == -1 || ss > s1)
            {
                ss = s1;
                id = i;
            }
        }
    }
    vis[id] = 1;
    DFS(cnt + 1, now ^ (1 << last), ss, id);
}

int main()
{
    int T, cas = 1;
    scanf("%d", &T);
    while (T--)
    {
        ansl = inf;
        scanf("%d", &n);
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%s", str[cnt].str);
            str[cnt].len = strlen(str[cnt].str);
            for (int j = 0; j < cnt; j++)
            {
                if (strstr(str[j].str, str[cnt].str) != NULL)
                {
                    cnt--;
                    break;
                }
                if (strstr(str[cnt].str, str[j].str) != NULL)
                {
                    strcpy(str[j].str, str[cnt].str);
                    str[j].len = strlen(str[j].str);
                    cnt--;
                    break;
                }
            }
            cnt++;
        }
        n = cnt;
        sort(str, str + n);
        Init();
        for (int i = 0; i < (1 << n); i++)
            for (int j = 0; j < n; j++)
                if (dp[i][j] != inf && (i & (1 << j)))
                    for (int k = 0; k < n; k++)
                        if (!(i & (1 << k)))
                            dp[i | (1 << k)][k] = min(dp[i | (1 << k)][k], dp[i][j] + str[k].len - dis[k][j]);
        int pos = 0;
        for (int i = 1; i < n; i++)
            if (dp[(1 << n) - 1][i] < dp[(1 << n) - 1][pos])
                pos = i;
        memset(vis, 0, sizeof(vis));
        vis[pos] = 1;
        ans = "";
        DFS(1, (1 << n) - 1, string(str[pos].str), pos);
        printf("Scenario #%d:\n", cas++);
        printf("%s\n", ans.c_str());
        printf("\n");
    }
    return 0;
}