Cod sursa(job #2594811)

Utilizator betybety bety bety Data 6 aprilie 2020 17:30:11
Problema ADN Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.66 kb
#include <iostream>

#include<cstdio>

#include<fstream>

#include<string>

using namespace std;

int wdfs(int node,int sgn,int fr)

{

    int ok[100];

    for(int i=1;i<=node;++i)

    for(int j=node+1;j<=2*node;++j)

    if(ok[i]==ok[j])

    return sgn+fr%2;

}

ifstream fin("adn.in");

ofstream fout("adn.out");

const int N=18;

int cost[N][N];

string s[N];

int dp[N][1<<N];

struct previous{

  char id;

  int mask;

};

previous prv[N][1<<N];

const int LENMAX=30005;

const int INF=300000005;

int lsp[LENMAX];

int included[N];

int n;

int calculatelps(int id1,int id2){

  lsp[0]=lsp[1]=0;



  for(int i=2;i<s[id1].size();i++){

    int poz=lsp[i-1];

    while( s[id1][poz+1]!=s[id1][i] && poz){

      poz=lsp[poz];

    }

    if( s[id1][poz+1]==s[id1][i]){

      lsp[i]=poz+1;

    }

    else

      lsp[i]=0;

  }

  int poz=0;

  for(int i=1;i<s[id2].size();i++){

    while( s[id1][poz+1]!=s[id2][i] && poz){

      poz=lsp[poz];

    }

    if( s[id1][poz+1]==s[id2][i]){

      poz++;

    }

    else

      poz=0;

    if(poz==s[id1].size()-1){

      included[id2]|=(1<<id1);

    }

  }

  return poz;

}

int noumask;

int bit;

void afis(int id,int mask){

  if(prv[id][mask].id==-1 || mask==0){

    for(int i=1;i<s[id].size();i++)

      fout<<s[id][i];

    return;

  }

  afis(prv[id][mask].id,prv[id][mask].mask);

  for(int i=s[id].size()-cost[prv[id][mask].id][id];i<s[id].size();i++)

    fout<<s[id][i];

}

int main()

{

  fin>>n>>ws;

  for(int i=0;i<n;i++){

    fin>>s[i];

    s[i]=" "+s[i];

  }

  for(int i=0;i<n;i++){

    included[i]=(1<<i);

    for(int j=0;j<n;j++){

      if(i!=j){

        cost[i][j]=s[j].size()-1-calculatelps(j,i);

      }

    }

  }

  for(int i=0;i<n;i++){

    for(int m=0;m<1<<n;m++){

      dp[i][m]=INF;

    }

  }

  for(int i=0;i<n;i++){

    dp[i][included[i]]=s[i].size()-1;

    prv[i][included[i]].id=-1;

    prv[i][included[i]].mask=-1;

  }

  for(int mask=0;mask<1<<n;mask++){

    for(int i=0;i<n;i++){

      if(mask & (1<<i) && dp[i][mask]!=INF){

        for(int j=0;j<n;j++){

          if(!(mask&(1<<j)) && dp[j][mask|included[j]]>dp[i][mask]+cost[i][j]){

            dp[j][mask|included[j]]=dp[i][mask]+cost[i][j];

            prv[j][mask|included[j]]={i,mask};

          }

        }

      }

    }

  }

  int sol=INF,idsol;

  for(int i=0;i<n;i++){

    if(sol>dp[i][(1<<n)-1]){

      sol=dp[i][(1<<n)-1];

      idsol=i;

    }

  }

  afis(idsol,(1<<n)-1);

  return 0;

}