Cod sursa(job #3247069)

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

const std :: string FILENAME = "adn";

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

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

const int NMAX = 18;

const int DIM = 3e4 + 5;

const int INF = 1e9;

short n;

int cnt;

bool ok;

std :: vector <short> pi(2 * DIM);

std :: vector <std :: string> v(NMAX);

std :: bitset <NMAX> fr;

std :: vector <std :: vector <short>> dist(NMAX, std :: vector <short>(NMAX));

std :: vector <std :: vector <std :: string>> dp((1 << NMAX), std :: vector <std :: string>(NMAX));

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

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

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

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

        pi[i] = j;
    }

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

    return k;
}

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

    for(int i = 1; i < s.size(); i ++)
    {
        short 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(short i = 0; i < n; i ++)
    {
        f >> v[i];
    }

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

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

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

                break;
            }
        }

        fr[i] = ok;
    }

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

    n = cnt;

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

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

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

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

    cnt = INF;

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

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

            return 0;
        }
    }

    return 0;
}