Pagini recente » Cod sursa (job #1720531) | Cod sursa (job #2978244) | Cod sursa (job #2127255) | Cod sursa (job #1524367) | Cod sursa (job #776041)
Cod sursa(job #776041)
/* ADN */
#include<cstdio>
#include<list>
#include<cstring>
using namespace std;
int n,i,j,k,sol;
char adn[20][300001],buff[40];
int l[20],exclude[20],start,maxim,nr,aux;
int cost[20][20];
int mat[300000][20];
int trace[300000][20];
int vtr[20],StartMax,iMax,jMax,LocalMax,GlobalMax,xi,xj,interval;
list<int> L[20];
list<int>::iterator it;
void compara(int x, int y)
{int ii,jj;
ii=0; jj=0;
int gasit=0;
while(ii<l[x])
{ if(adn[x][ii]!=adn[y][jj])
jj=0;
if(adn[x][ii]==adn[y][jj])
jj++;
ii++;
if(jj==l[y])
{gasit=1; break;}
}
if(gasit==0)
{cost[x][y]=jj;
L[y].push_back(x);}
else
exclude[y]=1;
}
int main()
{freopen("adn.in","r",stdin);
freopen("adn.out","w",stdout);
scanf("%d\n",&n);
for(i=0; i<n; i++)
{gets(adn[i]);
l[i]=strlen(adn[i]);}
for(i=0; i<n; i++)
for(j=0; j<n; j++)
if(i!=j && exclude[j]==0)
compara(i,j);
maxim=0;
for(start=0; start<n; start++)
if(exclude[start]==0)
{
LocalMax=0;
for(i=10; i<(1<<n); i++)
for(j=0; j<n; j++)
{mat[i][j]=0;
trace[i][j]=0;}
for(i=0; i<n; i++)
if(exclude[i]==0)
{mat[(1<<start | 1<<i)][i]=cost[start][i];
}
for(i=10; i<(1<<n); i++)
for(j=0; j<n; j++)
if(exclude[j]==0 && i&(1<<j) && i&(1<<start) && j!=start)
for(it=L[j].begin(); it!=L[j].end(); it++)
if(i&(1<<(*it)) && *it!=start)
{
if(exclude[*it]==0 && mat[i][j]<mat[i^(1<<j)][*it]+cost[*it][j])
{mat[i][j]=mat[i^(1<<j)][*it]+cost[*it][j];
if(mat[i][j]>LocalMax)
{LocalMax=mat[i][j];
iMax=i;
jMax=j;}
trace[i][j]=*it;}
}
if(GlobalMax<LocalMax)
{GlobalMax=LocalMax;
StartMax=start;
xi=iMax;
xj=jMax;
nr=0;
vtr[nr]=xj;
while(trace[xi][xj]!=0)
{nr++;
vtr[nr]=trace[xi][xj];
aux=xj;
xj=trace[xi][xj];
xi=xi^(1<<aux);
}
}
}
printf("%s",adn[StartMax]);
interval=cost[StartMax][vtr[nr]];
for(j=nr; j>=0; j--)
{for(i=interval; i<l[vtr[j]]; i++)
printf("%c",adn[vtr[j]][i]);
if(j>0)
interval=cost[vtr[j]][vtr[j-1]];
}
return 0;
}