Cod sursa(job #253203)

Utilizator 630r63Ilinca George Mihai 630r63 Data 5 februarie 2009 15:52:22
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.41 kb
   #include <cstdio>  
   #include <cstring>  
     
   const int NMAX = 20;  
   const int LMAX = 30002;  
   const int CFGMAX = 262130;  
   const int INF = 1000000000;  
   #define NMAX 20  
   #define LMAX 30002  
   #define CFGMAX 262130  
   #define INF 1000000000  
   const int mask[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072};  
     
   int N;  
   int length[NMAX],P[NMAX][LMAX];  
   char seq[NMAX][LMAX];  
   int com[NMAX][NMAX];  
   bool mark[NMAX];  
   int C[CFGMAX][NMAX],last[CFGMAX][NMAX];  
     
   void read_data() {  
       char aux[5];  
       fgets(aux,5,stdin);  
       sscanf(aux,"%d",&N);  
       for (int i=0; i<N; i++) {  
           scanf("%s",seq[i]+1);  
           length[i]=strlen(seq[i]+1);  
       }  
   }  
     
   void prefix ( char *sir, int lung, int *P ) {  
       int k=0;  
       P[1]=0;  
       for (int q=2; q<=lung; ++q) {  
           while (k>0 && sir[q]!=sir[k+1]) k=P[k];  
           if (sir[q]==sir[k+1]) k++;  
           P[q]=k;  
       }  
   }  
     
   int KMP ( char *sir, int lsir, char *subsir, int lsubsir, int *P ) {  
       int k=0;  
       for (int q=1; q<=lsir; ++q) {  
           while (k>0 && sir[q]!=subsir[k+1]) k=P[k];  
           if (sir[q]==subsir[k+1]) k++;  
           if (k==lsubsir) return -1;  
       }  
       return k;  
   }  
     
   void DP() {  
       int cfg = 1 << N;  
       for (int i=0; i<cfg; ++i)  
           for (int j=0; j<N; ++j)  
               if (!(i&mask[j]))  
                   C[i][j]=INF; else  
               if(i==mask[j])  
                   C[i][j]=length[j];  
               else {  
                   C[i][j]=INF;  
                   for(int k=0; k<N; ++k)  
                       if (C[i^mask[j]][k]!=INF && C[i][j]>C[i^mask[j]][k]+length[j]-com[k][j]) {  
                           C[i][j]=C[i^mask[j]][k]+length[j]-com[k][j];  
                           last[i][j]=k;  
                       }  
               }  
   }  
     
   void write_string ( char *s, int begin, int end ) {  
       for (int i=begin; i<=end; ++i) fputc(s[i],stdout);  
   }  
     
   void write ( int i, int j ) {  
       if(i==mask[j])  
           write_string(seq[j],1,length[j]);  
       else {  
           write(i^mask[j],last[i][j]);  
           write_string(seq[j],com[last[i][j]][j]+1,length[j]);  
       }  
   }  
     
   void write_solution() {  
       int cfg=0, min=INF, p=-1;  
       for (int i=0; i<N; i++)  
           if (mark[i]==false)  
               cfg|=mask[i];  
      for (int i=0; i<N; i++)  
           if (mark[i]==false && min>C[cfg][i]) {  
               min=C[cfg][i];  
               p=i;  
           }  
       write(cfg,p);  
   }  
     
   int main() {  
       freopen("adn.in","r",stdin);  
       freopen("adn.out","w",stdout);  
      read_data();  
       for(int i=0; i<N; i++) {  
          prefix(seq[i],length[i],P[i]);  
     }  
      for(int i=0; i<N; i++) {  
          for(int j=0; j<N; j++) {  
              if(i==j)  
                  com[i][j]=0;  
              else {  
                  com[i][j]=KMP(seq[i],length[i],seq[j],length[j],P[j]);  
                  if(com[i][j]==-1)  
                      mark[j]=true;  
              }  
          }  
      }  
      DP();  
      write_solution();  
      return 0;  
  }