Cod sursa(job #855943)

Utilizator tzipleatudTudor Tiplea tzipleatud Data 15 ianuarie 2013 20:36:54
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <fstream>
#include <cstring>
#define NM 20
#define LM 30001
#define INF 0x3f3f3f3f

using namespace std;

ifstream f("adn.in");
ofstream g("adn.out");

int N;
int i,j,k;
int a,b;
int NrPos, ANSPos;
int Size[NM];
char Sir[NM][LM];
int Cost[NM][NM];
int DP[(1 << 18)+23][NM];
int PI[NM][LM];
bool Included[NM];

void DoPrefix (int k)
{
    int i,j;

    for (i=2, j=0, PI[k][1]=0; i<=Size[k]; i++)
    {
        while (j!=0 && Sir[k][j+1]!=Sir[k][i])
            j=PI[k][j];

        if (Sir[k][j+1]==Sir[k][i])
            j++;

        PI[k][i]=j;
    }
}

int GetIntersection (int i, int j)
{
    int k,q;

    for (k=1, q=0; k<=Size[i]; k++)
    {
        while (q!=0 && Sir[j][q+1]!=Sir[i][k])
            q=PI[j][q];

        if (Sir[j][q+1]==Sir[i][k])
            q++;
    }

    return q;
}

void Print (int Conf, int P)
{
    if (Conf==(1 << (P-1)))
    {
        g << Sir[P]+1;
        return;
    }

    int NConf=Conf^(1 << (P-1));

    for (int i=1; i<=N; i++)
        if (!Included[i] && (Conf&(1 << (i-1)))!=0 && DP[NConf][i]+Cost[i][P]==DP[Conf][P])
        {
            Print(NConf, i);
            g << Sir[P]+1+Cost[i][P];
        }
}

int main ()
{
    f >> N;

    for (i=1; i<=N; i++)
    {
        f >> (Sir[i]+1);
        Size[i]=strlen(Sir[i]+1);
        DoPrefix(i);
    }

    for (i=1; i<=N; i++)
        for (j=i+1; j<=N; j++)
        {
            a=GetIntersection(i, j);
            b=GetIntersection(j, i);

            if (a==Size[j])
                Included[j]=1;

            if (b==Size[i] && a!=Size[j])
                Included[i]=1;

            Cost[i][j]=-b;
            Cost[j][i]=-a;
        }

    memset(DP, INF, sizeof(DP));

    for (i=1; i<=N; i++)
        if (!Included[i])
        {
            DP[1 << (i-1)][i]=0;
            ANSPos|=(1 << (i-1));
        }

    NrPos=(1 << N);

    for (i=1; i<NrPos; i++)
        for (j=1; j<=N; j++)
            if (!Included[j] && (i&(1 << (j-1)))!=0)
                for (k=1; k<=N; k++)
                    if (!Included[k] && ((1 << (k-1))&i)==0 && DP[i|(1 << (k-1))][k]>DP[i][j]+Cost[j][k])
                        DP[i|(1 << (k-1))][k]=DP[i][j]+Cost[j][k];

    for (i=1, j=1; i<=N; i++)
        if (DP[ANSPos][i]<DP[ANSPos][j])
            j=i;

    Print(ANSPos, j);

    g << '\n';

    f.close();
    g.close();

    return 0;
}