Cod sursa(job #1236051)

Utilizator george_stelianChichirim George george_stelian Data 1 octombrie 2014 11:41:40
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <cstdio>
#include <cstring>

using namespace std;

const int maxlen=30001;
char v[20][maxlen],vaz[20];
int cost[20][20],v1[20],din[270000][19],tata[270000][19],sol[20],n,i,j,q,minn,nrsol,lim,nr;

int kmp(char v[maxlen],char v1[maxlen])
{
    int pi[maxlen],k=-1,i,n=strlen(v),m=strlen(v1);
    pi[0]=-1;
    for(i=1;i<n;i++)
    {
        while(k>-1 && v[k+1]!=v[i]) k=pi[k];
        if(v[k+1]==v[i]) k++;
        pi[i]=k;
    }
    k=-1;
    for(i=0;i<m;i++)
    {
        while(k>-1 && v[k+1]!=v1[i]) k=pi[k];
        if(v[k+1]==v1[i]) k++;
        if(k==n-1) return 0;
    }
    return n-1-k;
}

int main()
{
    freopen("adn.in", "r", stdin);
    freopen("adn.out", "w", stdout);
    scanf("%d\n",&n);
    for(i=0;i<n;i++) scanf("%s\n",v[i]);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            if(i!=j)
            {
                cost[i][j]=kmp(v[j],v[i]);
                if(cost[i][j]==0) vaz[j]=1;
            }
    memset(din, 1000000, sizeof(din));
    for(i=0;i<n;i++)
        if(!vaz[i])
        {
            v1[nr]=i;
            din[1<<nr][nr]=strlen(v[i]);
            nr++;
        }
    lim=(1<<nr);
    for(i=1;i<lim;i++)
        for(j=0;j<nr;j++)
            if(i&(1<<j))
            {
                for(q=0;q<nr;q++)
                    if(!(i&(1<<q)))
                        if(din[i|(1<<q)][q]>din[i][j]+cost[v1[j]][v1[q]])
                        {
                            din[i|(1<<q)][q]=din[i][j]+cost[v1[j]][v1[q]];
                            tata[i|(1<<q)][q]=j;
                        }
            }
    minn=1000000;
    lim--;
    for(i=0;i<nr;i++)
        if(din[lim][i]<minn)
        {
            minn=din[lim][i];
            j=i;
        }
    i=j;
    while(lim>0)
    {
        sol[++nrsol]=v1[i];
        j=tata[lim][i];
        lim^=(1<<i);
        i=j;
    }
    lim=strlen(v[sol[nrsol]]);
    for(i=0;i<lim;i++) printf("%c",v[sol[nrsol]][i]);
    for(i=nrsol-1;i;i--)
    {
        lim=strlen(v[sol[i]]);
        for(j=lim-cost[sol[i+1]][sol[i]];j<lim;j++) printf("%c",v[sol[i]][j]);
    }
    return 0;
}