Cod sursa(job #562889)

Utilizator c_adelinaCristescu Adelina c_adelina Data 24 martie 2011 00:00:56
Problema ADN Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.79 kb
#include <cstdio>
#include <cstring>
int a[20][20],C[(1<<18)+9][20],bf[(1<<18)+9][20],n,x;

void rez(int secv,int poz)
{
	if (C[secv][poz]!=-1) return ;
	int i;
	if (!secv) return ;
	
	C[secv][poz]=1<<19;	
	for (i=1;i<=n;++i)
		if (secv&(1<<i))
			if ((i==x) && (secv!=1<<x)) continue; else
		{
			rez(secv^(1<<i),i);
			if (C[secv^(1<<i)][i]+a[i][poz]<C[secv][poz])
				C[secv][poz]=C[secv^(1<<i)][i]+a[i][poz],bf[secv][poz]=i;
		}
}
		


int main()
{
	int i,j,k,b,v[20],pi[30003],sol=3000000,ps[20];
	char s[20][30003];
	
	freopen("adn.in","r",stdin);
	freopen("adn.out","w",stdout);
	scanf("%d",&n);
	for (i=1;i<=n;++i)
		{scanf("%s",s[i]);v[i]=strlen(s[i]);}
	for (i=1;i<=n;++i)
	{
		k=0;pi[1]=0;         
		for (j=2;j<=v[i];++j) 
        { 
            for (;k&&(s[i][j-1]!=s[i][k]);) 
                k=pi[k]; 
               
            if (s[i][j-1]==s[i][k]) k++; 
            pi[j]=k; 
        } 
		k=0; 
		for (b=1;b<=n;++b) 
		if (b!=i)
		{
			
		for (j=1;j<=v[b];j++) 
        { 
            for (;k&&(s[b][j-1]!=s[i][k]);) k=pi[k]; 
   
            if (s[b][j-1]==s[i][k]) k++; 
			if (k==v[i]) break;
        } 
		a[b][i]=v[i]-k;
		}
	}

for (x=1;x<=n;++x)
{
	memset(C, -1, sizeof(C));
	C[0][x]=0;b=-1;
	for (j=1;j<=n;++j) 
		if (x!=j)
		{
			rez((((1<<(n+1))-1)^(1<<j))^1,j);
			C[(((1<<(n+1))-1)^(1<<j))^1][j]+=v[x];
			if (sol>C[(((1<<(n+1))-1)^(1<<j))^1][j]) 
				{sol=C[(((1<<(n+1))-1)^(1<<j))^1][j];b=j;}
		}
	if (b>0)
	{
		pi[pi[0]=1]=b;j=(((1<<(n+1))-1)^(1<<b))^1;
		while (b!=x)
			pi[++pi[0]]=(b=bf[j][b]),j=j^(1<<b);
	}
		
}
printf("%s",s[pi[pi[0]]]);
for (i=pi[0]-1;i;--i)
	if (a[pi[i+1]][pi[i]]==0) pi[i]=pi[i+1]; else
	printf("%s",s[pi[i]]+v[pi[i]]-a[pi[i+1]][pi[i]]);
printf("\n");

return 0;
}