Cod sursa(job #1291096)

Utilizator RaduVisanRadu Visan RaduVisan Data 12 decembrie 2014 11:20:47
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 kb
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;

const int NMAX = 19, LMAX = 30010, INF = 1000000;

int N, NotMask, Len[NMAX], PI[NMAX][LMAX], Cost[NMAX][NMAX], H[1 << NMAX][NMAX], From[1 << NMAX][NMAX];
char S[NMAX][LMAX];
bool Out[NMAX];

void DoPI(int Index)
{
    int Q = 0;
    for(int i = 2; i <= Len[Index]; ++ i)
    {
        while(Q && S[Index][Q + 1] != S[Index][i]) Q = PI[Index][Q];
        if(S[Index][Q + 1] == S[Index][i]) Q ++;
        PI[Index][i] = Q;
    }
}

void DoCost(int Index1, int Index2)
{
    int Q = 0;
    for(int i = 1; i <= Len[Index1]; ++ i)
    {
        while(Q && S[Index2][Q + 1] != S[Index1][i]) Q = PI[Index2][Q];
        if(S[Index2][Q + 1] == S[Index1][i]) Q ++;

        if(Q == Len[Index2])
        {
            Cost[Index1][Index2] = INF;
            Out[Index2] = 1;
            NotMask |= (1 << Index2);
            return ;
        }
    }
    Cost[Index1][Index2] = Q;
}

void Go(int Mask, int Str)
{
    if((Mask & (Mask - 1)) == 0)
    {
        for(int i = 1; i <= Len[Str]; ++ i) printf("%c", S[Str][i]);
        return ;
    }

    int PrevMask = Mask ^ (1 << Str), PrevStr = From[Mask][Str];
    Go(PrevMask, PrevStr);
    for(int i = Cost[PrevStr][Str] + 1; i <= Len[Str]; ++ i)
        printf("%c", S[Str][i]);
}

int main()
{
    freopen("adn.in", "r", stdin);
    freopen("adn.out", "w", stdout);

    scanf("%i\n", &N);
    for(int i = 0; i < N; ++ i)
    {
        gets(S[i] + 1);
        Len[i] = strlen(S[i] + 1);
        DoPI(i);
    }

    for(int i = 0; i < N; ++ i)
        for(int j = 0; j < N; ++ j)
            if(i != j)
                DoCost(i, j);

    for(int i = 1; i < (1 << N); ++ i)
        for(int j = 0; j < N; ++ j)
            H[i][j] = INF;

    for(int i = 0; i < N; ++ i)
        if(!Out[i])
            H[1 << i][i] = Len[i], From[1 << i][i] = 0;

    for(int i = 1; i < (1 << N); ++ i)
        for(int j = 0; j < N; ++ j)
            if( (i & (1 << j)) && H[i][j] != INF && !Out[j])
            {
                for(int k = 0; k < N; ++ k)
                    if(!Out[k] && !(i & (1 << k)) && H[i ^ (1 << k)][k] > H[i][j] + Len[k] - Cost[j][k])
                    {
                        H[i ^ (1 << k)][k] = H[i][j] + Len[k] - Cost[j][k];
                        From[i ^ (1 << k)][k] = j;
                    }
            }

    int StartMask = ((1 << N) - 1) ^ NotMask, MinCost = INF, Last;
    for(int i = 0; i < N; ++ i)
        if(H[StartMask][i] < MinCost)
            MinCost = H[StartMask][i], Last = i;

    Go(StartMask, Last);
}