ai编的程序(提交上去竟然是对的）

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
#include <string>
using namespace std;

const int MAXN = 12;
const int MAXLEN = 50;

int n;
vector<string> strings;
int overlap[MAXN][MAXN];  // overlap[i][j] 表示字符串i的后缀与字符串j的前缀的最大重叠长度
int dp[1 << MAXN][MAXN];  // dp[mask][i] 表示访问了mask中的字符串，且以第i个字符串结尾的最短长度
pair<int, int> parent[1 << MAXN][MAXN];  // 用于重构路径
string result_strings[1 << MAXN][MAXN];  // 存储对应的字符串结果

// 计算s1的后缀与s2的前缀的最大重叠长度
int get_overlap(const string& s1, const string& s2) {
    int max_overlap = min(s1.length(), s2.length());
    for (int i = max_overlap; i > 0; i--) {
        if (s1.substr(s1.length() - i) == s2.substr(0, i)) {
            return i;
        }
    }
    return 0;
}

// 合并两个字符串，考虑重叠部分
string merge_strings(const string& s1, const string& s2, int overlap_len) {
    return s1 + s2.substr(overlap_len);
}

int main() {
    ios::sync_with_stdio(false);
    cin >> n;
    
    strings.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> strings[i];
    }
    
    if (n == 1) {
        cout << strings[0] << endl;
        return 0;
    }
    
    // 预处理所有字符串对之间的重叠长度
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                overlap[i][j] = get_overlap(strings[i], strings[j]);
            }
        }
    }
    
    // 初始化DP数组
    for (int i = 0; i < (1 << n); i++) {
        for (int j = 0; j < n; j++) {
            dp[i][j] = INT_MAX;
        }
    }
    
    // 初始化：从每个字符串开始
    for (int i = 0; i < n; i++) {
        dp[1 << i][i] = strings[i].length();
        result_strings[1 << i][i] = strings[i];
        parent[1 << i][i] = make_pair(-1, -1);
    }
    
    // 动态规划
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i))) {
                continue;
            }
            if (dp[mask][i] == INT_MAX) {
                continue;
            }
            
            for (int j = 0; j < n; j++) {
                if (mask & (1 << j)) {
                    continue;
                }
                
                int new_mask = mask | (1 << j);
                int new_len = dp[mask][i] + strings[j].length() - overlap[i][j];
                
                // 构造新的字符串
                string new_string = merge_strings(result_strings[mask][i], strings[j], overlap[i][j]);
                
                // 更新条件：长度更短，或者长度相同但字典序更小
                if (new_len < dp[new_mask][j] || 
                    (new_len == dp[new_mask][j] && new_string < result_strings[new_mask][j])) {
                    dp[new_mask][j] = new_len;
                    result_strings[new_mask][j] = new_string;
                    parent[new_mask][j] = make_pair(mask, i);
                }
            }
        }
    }
    
    // 找到最优解
    int full_mask = (1 << n) - 1;
    int min_len = INT_MAX;
    int last_idx = -1;
    string best_result = "";
    
    for (int i = 0; i < n; i++) {
        if (dp[full_mask][i] < min_len) {
            min_len = dp[full_mask][i];
            last_idx = i;
            best_result = result_strings[full_mask][i];
        } else if (dp[full_mask][i] == min_len && result_strings[full_mask][i] < best_result) {
            last_idx = i;
            best_result = result_strings[full_mask][i];
        }
    }
    
    cout << best_result << endl;
    
    return 0;
}

看不懂思密达