Cod sursa(job #776041)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 9 august 2012 18:28:12
Problema ADN Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
/* 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;
}