Cod sursa(job #2818370)

Utilizator Iulia_DianaIulia Diana Iulia_Diana Data 15 decembrie 2021 22:32:36
Problema ADN Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.22 kb
#include <fstream>
#include <cstring>
#include <algorithm>
using namespace std;
ifstream fin("adn.in");
ofstream fout("adn.out");
#define Max 32000
int main()
{

    int i,j,n,k,s,mx=0,p[20],pmax[20],D[20][20],L[20];
    char cuv[20][Max],c[Max];
    fin>>n;
    for (i=0;i<n;i++)
        {fin>>cuv[i]; L[i]=strlen(cuv[i]);}
    for (i=0;i<n;i++)
        for (j=i+1;j<n;j++)
            if (L[i]<L[j])
                {swap(cuv[i],cuv[j]); swap(L[i],L[j]);}
    for (i=0;i<n;i++)
        for (j=i+1;j<n;j++)
            if (strstr(cuv[i],cuv[j]))  L[j]=0;
    for (i=0;i<n;i++)
        if (L[i]==0)
            {swap(L[i],L[n-1]); n--;}
    for (i=0;i<n;i++) {
           strcpy(c,cuv[i]);
           for (j=0;j<n;j++) {
               k=min(L[i],L[j]);
               while (k>0 && strncmp(c+L[i]-k,cuv[j],k)!=0)k--;
               D[i][j]=k;
           }
     }
    for (i=0;i<n;i++) p[i]=i;
    do {
            s=0;
            for (i=1;i<n;i++) s+=D[p[i-1]][p[i]];
            if (s>mx)
                {mx=s; for(j=0;j<n;j++) pmax[j]=p[j];}
    } while (next_permutation(p,p+n));
    fout<<cuv[pmax[0]];
    for(i=1;i<n;i++) {strcpy(c,cuv[pmax[i]]);fout<<c+D[pmax[i-1]][pmax[i]];}
    return 0;
}