Cod sursa(job #1404595)

Utilizator Ionut228Ionut Calofir Ionut228 Data 28 martie 2015 13:10:20
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.59 kb
#include <fstream>
#include <cstring>
#include <algorithm>

using namespace std;

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

const int INF = 0x3f3f3f3f;

char s[20][30005], snul[11];
int N, Ns[20], lim;
int cost[20][20], dp[263000][20], TT[263000][20];
int pi[30005];
bool used[20];

void make_prefix(char sir[])
{
    int lg = strlen(sir + 1);
    int k = 0;
    pi[1] = 0;

    for (int i = 2; i <= lg; ++i)
    {
        while (k > 0 && sir[k + 1] != sir[i])
            k = pi[k];
        if (sir[k + 1] == sir[i])
            ++k;
        pi[i] = k;
    }
}

int cost_kmp(char A[], char B[])
{
    int lgA = strlen(A + 1);
    int lgB = strlen(B + 1);
    int k = 0;
    pi[1] = 0;

    for (int i = 1; i <= lgB; ++i)
    {
        while (k > 0 && A[k + 1] != B[i])
            k = pi[k];
        if (A[k + 1] == B[i])
            ++k;

        if (k == lgA)
            return lgA;
    }

    return k;
}

void deleteSiruri()
{
    for (int i = 1; i <= N; ++i)
    {
        make_prefix(s[i]);
        for (int j = 1; j <= N; ++j)
            if (i != j && cost_kmp(s[i], s[j]) == Ns[i])
            {
                used[i] = true;
                break;
            }
    }
}

void makeCost()
{
    for (int i = 1; i <= N; ++i)
    {
        if (used[i])
            continue;
        make_prefix(s[i]);
        for (int j = 1; j <= N; ++j)
        {
            if (used[j] || i == j)
                continue;
            //cost[i][j] = cost_kmp(s[i], s[j]);
            cost[j][i] = cost_kmp(s[i], s[j]);
        }
    }
}

void path(int pos, int l)
{
    if (!TT[l][pos])
    {
        for (int i = 1; i <= Ns[pos]; ++i)
            fout << s[pos][i];
        return;
    }
    path(TT[l][pos], l - (1 << (pos - 1)));

    for (int i = cost[TT[l][pos]][pos] + 1; i <= Ns[pos]; ++i)
        fout << s[pos][i];
}

void solve()
{
    for (int i = 1; i <= (1 << N); ++i)
        for (int j = 1; j <= N; ++j)
            dp[i][j] = INF;

    for (int i = 1; i <= N; ++i)
        if (!used[i])
            dp[1 << (i - 1)][i] = Ns[i];

    lim = 0;
    for (int i = 1; i <= N; ++i)
        if (!used[i])
            lim += (1 << (i - 1));

    for (int mask = 1; mask <= (1 << N); ++mask)
    {
        for (int i = 1; i <= N; ++i)
        {
            if (used[i])
                continue;
            if (mask & (1 << (i - 1)))
            {
                for (int j = 1; j <= N; ++j)
                {
                    if (used[j] || i == j)
                        continue;
                    if (mask & (1 << (j - 1)))
                    {
                        if (dp[mask - (1 << (i - 1))][j] + Ns[i] - cost[j][i] < dp[mask][i])
                        {
                            dp[mask][i] = dp[mask - (1 << (i - 1))][j] + Ns[i] - cost[j][i];
                            TT[mask][i] = j;
                        }
                        //dp[mask][i] = min(dp[mask][i], dp[mask - (1 << (i - 1))][j] + Ns[i] - cost[j][i]);
                    }
                }
            }
        }
    }
    int maxim = INF, pos;
    for (int i = 1; i <= N; ++i)
        if (dp[lim][i] < maxim)
        {
            maxim = dp[lim][i];
            pos = i;
        }
    path(pos, lim);
}

int main()
{
    fin >> N;
    fin.getline(snul, 11);
    for (int i = 1; i <= N; ++i)
        fin.getline(s[i] + 1, 30005);
    for (int i = 1; i <= N; ++i)
        Ns[i] = strlen(s[i] + 1);

    deleteSiruri();
    makeCost();
    solve();

    fin.close();
    fout.close();
    return 0;
}