Cod sursa(job #2611684)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 7 mai 2020 13:54:16
Problema ADN Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.12 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("adn.in");
ofstream fout("adn.out");

const int INF = 1e9;
const int DIM = 20;
const int LEN = 3e4 + 7;

vector <string> s;

int add[DIM][DIM];
int cost[DIM][DIM];
bool ok[DIM];
int pos[DIM];
int phi[DIM];

void get_phi(int x)
{
    int k = 0;
    int p = s[x].size() - 1;

    for(int i = 2; i <= p; ++i)
    {
        while(k && s[x][k + 1] != s[x][i])
        {
            k = phi[k];
        }

        if(s[x][k + 1] == s[x][i])
            ++k;

        phi[i] = k;
    }
}

int get_cost(int x, int y)
{
    int n = s[x].size() - 1;
    int m = s[y].size() - 1;

    int k = 0;

    for(int i = 1; i <= m; ++i)
    {
        while(k && s[x][k + 1] != s[y][i])
            k = phi[k];

        if(s[x][k + 1] == s[y][i])
            ++k;

        if(k == n)
        {
            k = phi[k];
            ok[x] = false;
        }
    }

    return n - k;
}

int dp[(1 << DIM)][DIM];
int from[(1 << DIM)][DIM];

vector <string> res;

void print(int mask, int last)
{
    if(from[mask][last] == -1)
    {
        for(int i = 1; i < res[last].size(); ++i)
            fout << res[last][i];

        return ;
    }

    print((mask ^ (1 << last)), from[mask][last]);

    int p = add[from[mask][last]][last];

    for(int i = res[last].size() - p; i < res[last].size(); ++i)
        fout << res[last][i];
}

main()
{
    int n;
    fin >> n;

    s.resize(n);

    for(auto& i : s)
    {
        fin >> i;

        i = ' ' + i;
    }

    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());

    n = s.size();

    for(int i = 0; i < n; ++i)
    {
        ok[i] = true;

        get_phi(i);

        for(int j = 0; j < n; ++j)
        {
            if(i != j)
                cost[j][i] = get_cost(i, j);
        }
    }

    int id = -1;

    for(int i = 0; i < n; ++i)
    {
        if(ok[i] == true)
        {
            res.emplace_back(s[i]);
            pos[i] = ++id;
        }
    }

    for(int i = 0; i < n; ++i)
        if(ok[i] == true)
            for(int j = 1; j < n; ++j)
                if(ok[j])
                    add[pos[i]][pos[j]] = cost[i][j], add[pos[j]][pos[i]] = cost[j][i];

    n = id + 1;

    for(int i = 0; i < (1 << n); ++i)
        for(int j = 0; j < n; ++j)
        {
            dp[i][j] = INF;
            from[i][j] = -1;
        }

    for(int i = 0; i < n; ++i)
        dp[(1 << i)][i] = res[i].size() - 1;

    for(int i = 0; i < (1 << n); ++i)
        for(int j = 0; j < n; ++j)
            if(i & (1 << j))
                for(int k = 0; k < n; ++k)
                    if((i & (1 << k)) && k != j)
                        if(dp[i][j] > dp[i ^ (1 << j)][k] + add[k][j])
                        {
                            dp[i][j] = dp[i ^ (1 << j)][k] + add[k][j];
                            from[i][j] = k;
                        }

    pair <int, int> best = {INF, 0};

    for(int i = 0; i < n; ++i)
        best = min(best, {dp[(1 << n) - 1][i], i});

    print(((1 << n) - 1), best.second);
}