Cod sursa(job #1071791)

Utilizator crisbodnarCristian Bodnar crisbodnar Data 3 ianuarie 2014 14:50:35
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <memory.h>

#define Present(config, poz) ((config) & (1 << poz))
#define Out(config, poz) ((config) ^ (1 << poz))
#define tata Tat[conf][nod]

using namespace std;

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

const int Nmax = 18;
const int Mmax = 30100;
const int oo = 0x3f3f3f3f;

int N, sters, maxconf, PI[Nmax][Mmax], Lg[Nmax], CST[Nmax][Nmax], DP[(1 << Nmax)][Nmax], Tat[(1 << Nmax)][Nmax];
char s[Nmax][Mmax];

void Build_PI(int i)
{
    for(int q = 2, k = 0; q <= Lg[i]; q++)
    {
        while(k && s[i][k+1] != s[i][q])
            k = PI[i][k];
        if(s[i][k+1] == s[i][q]) k++;
        PI[i][q] = k;
    }
}

int KMP(int x, int y)
{
    int q = 0;
    for(int i = 1; i <= Lg[y]; i++)
    {
        while(q && s[x][q+1] != s[y][i])
            q = PI[x][q];
        if(s[x][q+1] == s[y][i]) q++;
        if(q == Lg[x])
        {
            sters |= (1 << x);
            return q;
        }
    }
    return q;
}

void Afisare(int conf, int nod)
{
    if(tata == -1)
    {
        fout<<s[nod] + 1;
        return;
    }
    Afisare(Out(conf, nod), tata);
    for(int i = CST[tata][nod] + 1; i <= Lg[nod]; i++)
        fout<<s[nod][i];
}

int main()
{
    fin>>N;
    for(int i=0; i < N; i++)
    {
        fin>>(s[i] + 1);
        Lg[i] = strlen(s[i] + 1);
        Build_PI(i);
    }

    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            if(i != j) CST[i][j] = KMP(j, i);

    memset(DP, oo, sizeof DP);
    memset(Tat, -1, sizeof Tat);

    for(int i=0; i < N; i++)
        DP[(1 << i)][i] = Lg[i];

    maxconf = (1 << N); int nr;
    for(int conf = 0; conf < maxconf; conf++)
        for(int i = 0; i < N; i++)
            if(Present(conf, i))
                for(int j = 0; j < N; j++)
                    if(i != j && Present(conf, j))
                        if(DP[conf][i] > (nr = DP[Out(conf, i)][j] - CST[j][i] + Lg[i]))
                        {
                            DP[conf][i] = nr;
                            Tat[conf][i] = j;
                        }

    int finalconf = (maxconf - 1) & (~sters), psol = 0;
    for(int i=1; i < N; i++)
        if(DP[finalconf][psol] > DP[finalconf][i]) psol = i;
    Afisare(finalconf, psol);
    return 0;
}