Cod sursa(job #1119825)

Utilizator chiriacandrei25Chiriac Andrei chiriacandrei25 Data 24 februarie 2014 20:16:14
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.62 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],ok[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 int Cost(int p1, int p2, char a[], char b[])
{
    int i,k=0,ok=1;
    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
        return -1;
}

int main()
{
    int i,j,k,p,y,okk;
    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)
                if(Cost(i,j,a[i],a[j])==-1)
                {
                    ok[i]=-1;
                    break;
                }

    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)
    {
        for(okk=1,y=0;y<N;++y)
            if(((1<<y)&i) && ok[y+1]==-1)
                okk=0;
        if(okk)
        {
            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];
                            }
        }
    }
    for(y=0;y<N;++y)
        if(ok[y+1]==-1)
            Vmax-=(1<<y);
    if(Vmax<0)
        Vmax=10;
    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>0)
    {
        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;
}