Cod sursa(job #3247058)

Utilizator Sasha_12454Eric Paturan Sasha_12454 Data 5 octombrie 2024 14:27:43
Problema ADN Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.17 kb
#include <bits/stdc++.h>

const std :: string FILENAME = "adn";

std :: ifstream f (FILENAME + ".in");

std :: ofstream g (FILENAME + ".out");

const int NMAX = 20;

const int DIM = 3e4 + 5;

const int INF = 1e9;

int n;

int cnt;

bool ok;

int pi[2 * DIM];

std :: string v[NMAX];

std :: bitset <NMAX> fr;

std :: string dist[NMAX][NMAX];

std :: string dp[(1 << 18)][NMAX];

inline std :: string pref(std :: string a, std :: string b)
{
    std :: string s = b + "#" + a;

    for(int i = 1; i < s.size(); i ++)
    {
        int j = pi[i - 1];

        while(j > 0 && s[i] != s[j])
        {
            j = pi[j - 1];
        }

        if(s[i] == s[j])
        {
            j ++;
        }

        pi[i] = j;
    }

    int k = pi[s.size() - 1];

    return b.substr(k);
}

inline bool continut(std :: string a, std :: string b)
{
    std :: string s = a + "#" + b;

    for(int i = 1; i < s.size(); i ++)
    {
        int j = pi[i - 1];

        while(j > 0 && s[i] != s[j])
        {
            j = pi[j - 1];
        }

        if(s[i] == s[j])
        {
            j ++;
        }

        pi[i] = j;
    }

    for(int i = 0; i < s.size(); i ++)
    {
        if(pi[i] == a.size())
        {
            return true;
        }
    }

    return false;
}

int main()
{

    f >> n;

    for(int i = 0; i < n; i ++)
    {
        f >> v[i];
    }

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

        for(int j = 0; j < n; j ++)
        {
            if(i == j)
            {
                continue;
            }

            if(continut(v[i], v[j]))
            {
                ok = false;

                break;
            }
        }

        fr[i] = ok;
    }

    for(int i = 0; i < n; i ++)
    {
        if(fr[i])
        {
            v[cnt ++] = v[i];
        }
    }

    n = cnt;

    for(int i = 0; i < n; i ++)
    {
        for(int j = 0; j < n; j ++)
        {
            if(i == j)
            {
                continue;
            }

            dist[i][j] = pref(v[i], v[j]);
        }
    }

    for(int i = 0; i < n; i ++)
    {
        dp[(1 << i)][i] = v[i];
    }

    for(int mask = 0; mask < (1 << n); mask ++)
    {
        for(int i = 0; i < n; i ++)
        {
            if(mask & (1 << i))
            {
                for(int j = 0; j < n; j ++)
                {
                    if((mask ^ (1 << i)) & (1 << j))
                    {
                        if((dp[mask][i].size() == 0) || (dp[mask ^ (1 << i)][j].size() + dist[j][i].size() < dp[mask][i].size()))
                        {
                            dp[mask][i] = dp[mask ^ (1 << i)][j] + dist[j][i];
                        }
                    }
                }
            }
        }
    }

    cnt = INF;

    for(int i = 0; i < n; i ++)
    {
        cnt = std :: min(cnt, (int)dp[(1 << n) - 1][i].size());
    }

    for(int i = 0; i < n; i ++)
    {
        if((int)dp[(1 << n) - 1][i].size() == cnt)
        {
            g << dp[(1 << n) - 1][i];

            return 0;
        }
    }

    return 0;
}