Cod sursa(job #1133620)

Utilizator negreadumitruNegrea Dumitru negreadumitru Data 5 martie 2014 10:35:56
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.13 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;
}
    memset(dp, INF, sizeof(dp));
    for(m=1;m<(1<<n);m++)
    {
        for(i=0;i<n;i++)
        {
            if(!(m&(1<<i))) continue;
            if(!zs(m))
                dp[m][i]=sz[i], v[m][i]=i;
            ii=v[m][i];
            for(x=0;x<n;x++)
            {
                if(!(m&(1<<x)))
                {
                    if(dp[m|(1<<x)][x]>dp[m][i]+sz[x]-c[ii][x])
                    {
                        dp[m|(1<<x)][x]=dp[m][i]+sz[x]-c[ii][x];
                        nxt[m|(1<<x)][x]=i;
                        v[m|(1<<x)][x]=x;
                    }
                    if(b[ii][x]&&dp[m][i]<dp[m|(1<<x)][i])
                    {
                        dp[m|(1<<x)][x]=dp[m][i];
                        nxt[m|(1<<x)][x]=i;
                        v[m|(1<<x)][x]=ii;
                    }
                }
            }
        }
    }
    for(i=0;i<n;i++)
    {
        if(dp[(1<<n)-1][i]<sol)
        {
            sol=dp[(1<<n)-1][i];
            soli=i;
        }
    }
    for(m=(1<<n)-1;m;m^=(1<<p))
    {
        if(v[m][soli]==soli) nr[++nr[0]]=soli;
        p=soli;
        soli=nxt[m][soli];
    }
    //printf("%d\n", *min_element(dp[(2<<n)-2]+1, dp[(2<<n)-2]+n+1));
    printf("%s", a[nr[nr[0]]]+1);
    for(i=nr[0]-1;i>0;i--)
    {
        printf("%s", a[nr[i]]+c[nr[i+1]][nr[i]]+1);
    }
}
    {
        if(v[m][soli]==soli) nr[++nr[0]]=soli;
        p=soli;
        soli=nxt[m][soli];
    }
    //printf("%d\n", *min_element(dp[(2<<n)-2]+1, dp[(2<<n)-2]+n+1));
    printf("%s", a[nr[nr[0]]]+1);
    for(i=nr[0]-1;i>0;i--)
    {
        printf("%s", a[nr[i]]+c[nr[i+1]][nr[i]]+1);
    }
}