Cod sursa(job #562767)

Utilizator c_adelinaCristescu Adelina c_adelina Data 23 martie 2011 20:56:41
Problema ADN Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <cstdio>
#include <cstring>
int a[20][20],lung,now,x[20],p[20],C[(1<<18)+1][20],n;

void rez(int secv,int poz)
{
	if (C[secv][poz]!=-1) return ;
	int i;
	if (!secv)
 		{if (lung<now) {now=lung;for (i=0;i<=p[0];++i) x[i]=p[i];}
		 return ;
		}
	C[secv][poz]=90000000;	
	for (i=1;i<=n;++i)
		if (secv&(1<<i))
		{
			if (a[p[p[0]]][i]==0) rez(secv^1<<i,poz); else
				lung+=a[p[p[0]]][i],p[++p[0]]=i,rez(secv^1<<i,i),--p[0],lung-=a[p[p[0]]][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 (i=1;i<=n;++i)
	for (j=1;j<=n;++j) 
		if (i!=j)
		{
			lung=v[i]+a[i][j];
			memset(C, -1, sizeof(C));
			x[0]=p[0]=2;x[1]=p[1]=i;x[2]=p[2]=j;now=sol;
			rez(((((1<<(n+1))-1)^(1<<i))^(1<<j))^1,j);
			if (sol>now) 
				{sol=now;for (b=0;b<=x[0];++b) ps[b]=x[b];}
		}
printf("%s",s[ps[1]]);		
for (i=2;i<=ps[0];++i)
	printf("%s",s[ps[i]]+v[ps[i]]-a[ps[i-1]][ps[i]]);
printf("\n");

return 0;
}