Cod sursa(job #2594800)

Utilizator betybety bety bety Data 6 aprilie 2020 17:14:13
Problema ADN Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.3 kb
#include <bits/stdc++.h>



using namespace std;



ifstream fin ("adn.in");

ofstream fout ("adn.out");



const int NMAX = 20, LMAX = 30010;

int n, lg[NMAX], lps[NMAX][LMAX];

char sir[NMAX][LMAX];

int dist[NMAX][NMAX];

long long dp[1 << NMAX][NMAX], lgMin = LLONG_MAX;

int indAns[NMAX], nod;



void FindLPS(int ind)

{

    int j = 0;

    int i = 1;

    lps[ind][0] = 0;



    while (i < lg[ind])

    {

        if (sir[ind][i] == sir[ind][j])

        {

            lps[ind][i] = j + 1;

            i++;

            j++;

        }

        else

        {

            if (j != 0)

                j = lps[ind][j - 1];

            else

            {

                lps[ind][i] = 0;

                i++;

            }

        }

    }

}



void CalcDist(int ind1, int ind2)

{

    int i = 0;

    int j = 0;



    while (i < lg[ind1])

    {

        if (sir[ind1][i] == sir[ind2][j])

        {

            i++;

            j++;



            if (j == lg[ind2])

            {

                dist[ind1][ind2] = 0;

                return;

            }

        }

        else

        {

            if (j != 0)

                j = lps[ind2][j - 1];

            else

                i++;

        }

    }



    dist[ind1][ind2] = lg[ind2] - j;

}



void SolveDP()

{

    for (int mask = 1; mask < (1 << n); mask++)

        for (int i = 1; i <= n; i++)

            dp[mask][i] = LLONG_MAX;



    for (int i = 1; i <= n; i++)

        dp[1 << (i - 1)][i] = lg[i];



    for (int mask = 1; mask < (1 << n); mask++)

    {

        for (int i = 1; i <= n; i++)

        {

            if (mask & (1 << (i - 1)))

            {

                for (int j = 1; j <= n; j++)

                    if (i != j && (mask & (1 << (j - 1))))

                        dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << (i - 1))][j] + dist[j][i]);

            }

        }

    }



    for (int i = 1; i <= n; i++)

    {

        if (lgMin > dp[(1 << n) - 1][i])

        {

            lgMin = dp[(1 << n) - 1][i];

            nod = i;

        }

    }

}



void FindAns(int mask, int ind, long long val, int cnt)

{

    if (mask > 0)

    {

        for (int i = 1; i <= n; i++)

        {

            if ((mask & (1 << (i - 1))) && dp[mask][i] + dist[i][ind] == val)

            {

                indAns[cnt] = i;



                FindAns(mask ^ (1 << (i - 1)), i, val - dist[i][ind], cnt - 1);

                break;

            }

        }

    }

}



int main()

{

    fin >> n;

    for (int i = 1; i <= n; i++)

    {

        fin >> sir[i];

        lg[i] = strlen(sir[i]);

        FindLPS(i);

    }



    for (int i = 1; i <= n; i++)

    {

        for (int j = 1; j <= n; j++)

            if (i != j)

                CalcDist(i, j);

    }



    SolveDP();

    FindAns(((1 << n) - 1) ^ (1 << (nod - 1)), nod, dp[(1 << n) - 1][nod], n - 1);

    indAns[n] = nod;



    fout << sir[indAns[1]];

    for (int i = 2; i <= n; i++)

        fout << (sir[indAns[i]] + lg[indAns[i]] - dist[indAns[i - 1]][indAns[i]]);

    return 0;

}