Submission #50840597

---

Source Code Expand

/**
 *  @the_hyp0cr1t3
 *  02.03.2024 18:35
**/
#include <bits/stdc++.h>

auto chmin = [](auto &x, auto y) {
    x = std::min(x, y);
};

auto prefix_function(const std::string &s) {
    int n = s.size();
    std::vector<int> pi(n);
    for (int z = 1; z < n; z++) {
        int p = pi[z - 1];
        while (p and s[z] != s[p])
            p = pi[p - 1];
        pi[z] = p + (s[z] == s[p]);
    }
    return pi;
}

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);

    int n;
    std::cin >> n;
    std::vector<std::string> s(n);
    for (auto &x : s)
        std::cin >> x;

    std::vector d(n, std::vector<int>(n));
    std::vector dp(1 << n, std::vector<int>(n, 3e5));
    for (int i = 0; i < n; i++) {
        int m = 1 << i;
        for (int j = 0; j < n; j++) {
            auto pi = prefix_function(s[j] + '.' + s[i]);
            int a = s[i].length(), b = s[j].length();
            chmin(d[i][j], -pi.back());
            for (int k = 1; k <= a; k++)
                if (pi[b + k] == b) m |= 1 << j;
        }
        for (int j = m; j > 0; j = m & (j - 1))
            chmin(dp[j][i], (int)s[i].length());
    }

    for (int m = 1; m < 1 << n; m++) {
        for (int i = 0; i < n; i++) {
            if (~m >> i & 1) continue;
            for (int j = 0; j < n; j++) {
                if (m >> j & 1) continue;
                chmin(dp[m | (1 << j)][j], dp[m][i] + d[i][j] + (int)s[j].length());
            }
        }
    }

    std::cout << std::ranges::min(dp.back()) << '\n';
}

Submission Info

Judge Result