Cod sursa(job #954805)

Utilizator misinoonisim necula misino Data 30 mai 2013 01:51:39
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include<fstream>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("adn.in");
ofstream g("adn.out");
int  i,j,conf,l1,l2,n,pi,sol,c[20][20],d[1000000][20],pred[1000000][20],lg[20];
bool ok[20];
int poz[20][30100];
char s[20][30100];
inline void prefix(int x)
{
    int i,k=0;
    poz[x][1]=0;
    for(i=2;i<=lg[x];++i)
    {
        while(k&&s[x][k+1]!=s[x][i])
        k=poz[x][k];
        if(s[x][k+1]==s[x][i])
        ++k;
        poz[x][i]=k;
    }
}
inline int kmp(int x,int y)
{
    int i,k=0;
    for(i=1;i<=lg[x];++i)
    {
        while(k&&s[y][k+1]!=s[x][i])
        k=poz[y][k];
        if(s[y][k+1]==s[x][i])
        ++k;
        if(k==lg[y])
        return k;
    }
    return k;
}
inline void afiseaza(int conf,int p)
{
    if(conf==(1<<p))
    {
        g<<(s[p]+1);
        return;
    }
    afiseaza(conf^(1<<p),pred[conf][p]);
    g<<(s[p]+1-c[pred[conf][p]][p]);
}
int main()
{
    f>>n;
    for(i=0;i<n;++i)
    {
        f>>(s[i]+1);
        lg[i]=strlen(s[i]+1);
        prefix(i);
    }
    for(i=0;i<n;++i)
    for(j=i+1;j<n;++j)
    {
        l1=kmp(i,j);
        l2=kmp(j,i);
        c[i][j]=-l1;
        c[j][i]=-l2;
        if(l1==lg[j])
        ok[j]=1;
        else
        if(l2==lg[i])
        ok[i]=1;
    }
    memset(d,INF,sizeof(d));
    for(i=0;i<n;++i)
    if(!ok[i])
    {
        sol+=(1<<i);
        d[1<<i][i]=0;
    }
    for(conf=1;conf<(1<<n);++conf)
    for(i=0;i<n;++i)
    if(!ok[i]&&d[conf][i]<INF&&conf&(1<<i))
    for(j=0;j<n;++j)
    if(!ok[j]&&!(conf&(1<<j))&&d[conf^(1<<j)][j]>d[conf][i]+c[i][j])
    {
        d[conf^(1<<j)][j]=d[conf][i]+c[i][j];
        pred[conf^(1<<j)][j]=i;
    }
    pi=0;
    for(i=1;i<n;++i)
    if(d[sol][i]<d[sol][pi])
    pi=i;
    afiseaza(sol,pi);
    return 0;
}