Cod sursa(job #434145)

Utilizator DraStiKDragos Oprica DraStiK Data 5 aprilie 2010 09:44:51
Problema ADN Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <algorithm>
using namespace std;

#define INF 0x3f3f3f3f
#define LIM (1<<18)+5
#define MAX 30005
#define DIM 20

int best[LIM][DIM],ant[LIM][DIM],dst[DIM][DIM];
int lg[DIM],pi[DIM],newn[DIM];
int n,m,cost,rez,poz;
char buff[DIM][MAX];
bool inside[DIM];

void read ()
{
    int i;

    scanf ("%d",&n);
    for (i=1; i<=n; ++i)
    {
        scanf ("%s",buff[i]+1);
        lg[i]=strlen (buff[i]+1);
    }
}

inline void prefix (int x)
{
    int i,k;

    for (k=0, i=2; i<=lg[x]; ++i)
    {
        for ( ; k && buff[x][k+1]!=buff[x][i]; k=pi[k]);
        if (buff[x][k+1]==buff[x][i])
            ++k;
        pi[i]=k;
    }
}

inline int kmp (int x,int y)
{
    int i,k,ok;

    for (ok=k=0, i=1; i<=lg[y]; ++i)
    {
        for ( ; k && buff[x][k+1]!=buff[y][i]; k=pi[k]);
        if (buff[x][k+1]==buff[y][i])
            ++k;
        if (k==lg[x])
            ok=1;
        cost=k;
    }
    return ok;
}

void init ()
{
    int i,j;

    for (i=1; i<=n; ++i)
        for (j=1; j<=n; ++j)
            if (i!=j)
            {
                prefix (i);
                cost=0;
                if (kmp (i,j))
                    inside[i]=1;
                dst[j][i]=cost;
            }
    for (i=1; i<=n; ++i)
        if (!inside[i])
            newn[++m]=i;
}

void print (int x,int lv)
{
    int i;

    if (!lv)
        return ;
    print (ant[lv][x],lv^(1<<(x-1)));
    for (i=dst[newn[ant[lv][x]]][newn[x]]+1; i<=lg[newn[x]]; ++i)
		printf("%c",buff[newn[x]][i]);
}

void solve ()
{
    int i,j,k;

    memset (best,INF,sizeof (best));
    for (i=1; i<=m; i++)
        best[1<<(i-1)][i]=lg[newn[i]];
    for (i=0; i<(1<<m); ++i)
        for (j=1; j<=m; ++j)
            if (i&(1<<(j-1)))
				for (k=1; k<=m; ++k)
                    if (!(i&(1<<(k-1))))
                        if (best[i^(1<<(k-1))][k]>best[i][j]+lg[newn[k]]-dst[newn[j]][newn[k]])
                        {
                            best[i^(1<<(k-1))][k]=best[i][j]+lg[newn[k]]-dst[newn[j]][newn[k]];
                            ant[i^(1<<(k-1))][k]=j;
                        }
    rez=INF;
    for (i=1; i<=m; ++i)
		if (best[(1<<m)-1][i]<rez)
		{
			rez=best[(1<<m)-1][i];
			poz=i;
		}
    print (poz,(1<<m)-1);
}

int main ()
{
    freopen ("adn.in","r",stdin);
    freopen ("adn.out","w",stdout);

    read ();
    init ();
    solve ();
}