Cod sursa(job #2587481)

Utilizator AlexandruGabrielAliciuc Alexandru AlexandruGabriel Data 22 martie 2020 18:46:46
Problema ADN Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.07 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++)
        for (int j = lg[indAns[i]] - dist[indAns[i - 1]][indAns[i]]; j < lg[indAns[i]]; j++)
            fout << sir[indAns[i]][j];
    return 0;
}