Cod sursa(job #1197084)

Utilizator apopeid15Apopei Daniel apopeid15 Data 10 iunie 2014 18:57:10
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#define Nmax 30005

using namespace std;

int Vmax,N,pi[25][Nmax],len[25],c[25][25],dp[265000][20],r[265000][20],t[265000][20],s[20],sar[20];
char a[25][Nmax];

inline void Pi(int poz, char a[])
{
    int i,k=0;
    for(i=2;i<=len[poz];++i)
    {
        while(k && a[k+1]!=a[i])
            k=pi[poz][k];
        if(a[k+1]==a[i])
            ++k;
        pi[poz][i]=k;
    }
}

inline void Cost(int p1, int p2, char a[], char b[])
{
    int i,k=0,ok=1;
    if(c[p1][p2]>0)
        return;
    for(i=1;i<=len[p2];++i)
    {
        while(k && a[k+1]!=b[i])
            k=pi[p1][k];
        if(a[k+1]==b[i])
            ++k;
        if(k==len[p1])
        {
            ok=0;
            break;
        }
    }
    if(ok)
        c[p1][p2]=max(c[p1][p2],k);
    else
        c[p1][p2]=len[p1];
}

int main()
{
    int i,j,k,p,masca=0;
    freopen ("adn.in","r",stdin);
    freopen ("adn.out","w",stdout);
    scanf("%d", &N);
    Vmax=(1<<N)-1;
    for(i=1;i<=N;++i)
    {
        scanf("\n%s", (a[i]+1));
        len[i]=strlen(a[i]+1);
        Pi(i,a[i]);
    }
    for(i=1;i<=N;++i)
        for(j=1;j<=N;++j)
            if(i!=j)
            {
                Cost(i,j,a[i],a[j]);
                if(c[i][j]==len[i] && !(masca&(1<<(i-1))))
                    masca+=(1<<(i-1));
            }

    for(i=1;i<=Vmax;++i)
        for(j=1;j<=N;++j)
            dp[i][j]=2000000000;
    for(i=1;i<=N;++i)
        dp[(1<<(i-1))][i]=len[i];

    for(i=1;i<=Vmax;++i)
    {
        if(i&masca)
            continue;
        for(j=1;j<=N;++j)
            if((1<<(j-1))&i)
                for(k=1;k<=N;++k)
                    if(k!=j && ((1<<(k-1))&i))
                        if(dp[i][j]>dp[i-(1<<(j-1))][k]+len[j]-c[j][k])
                        {
                            dp[i][j]=dp[i-(1<<(j-1))][k]+len[j]-c[j][k];
                            r[i][j]=k; t[i][j]=c[j][k];
                        }
    }
    Vmax-=masca;
    k=dp[Vmax][1]; p=1;
    for(i=2;i<=N;++i)
        if(dp[Vmax][i]<k)
        {
            k=dp[Vmax][i];
            p=i;
        }
    while(Vmax)
    {
        s[++s[0]]=p;
        sar[s[0]]=t[Vmax][p];
        k=p;
        p=r[Vmax][p]; Vmax-=(1<<(k-1));
    }
    printf("%s", (a[s[s[0]]]+1));
    for(i=s[0]-1;i;--i)
        for(j=sar[i]+1;j<=len[s[i]];++j)
            printf("%c", a[s[i]][j]);
    printf("\n");
    return 0;
}