Cod sursa(job #3200691)

Utilizator Anul2024Anul2024 Anul2024 Data 5 februarie 2024 17:40:55
Problema ADN Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <fstream>
#define inf 540001
using namespace std;
ifstream fin ("adn.in");
ofstream fout ("adn.out");
string s[19],sir,ss;
int poz,p,ok,n,i,j,pr[60002],nr,minim,l[19][19],dp[(1<<18)][19];
short int t[(1<<18)][19];
void f (int poz,int conf)
{
    if (t[conf][poz]==-1)
    {
        for (int j=1; j<s[poz].size (); j++)
            fout<<s[poz][j];
    }
    else
    {
        int ant=t[conf][poz];
        f (ant,conf-(1<<poz));
        for (int j=l[ant][poz]; j>0; j--)
            fout<<s[poz][s[poz].size ()-j];
    }
}
bool match (string &a,string &b)
{
    int l=0;
    pr[1]=0;
    for (int i=2; i<a.size (); i++)
    {
        while (l>0&&a[i]!=a[l+1])
            l=pr[l];
        if (a[i]==a[l+1])
            l++;
        pr[i]=l;
    }
    l=0;
    for (int i=1; i<b.size (); i++)
    {
        while (l>0&&b[i]!=a[l+1])
            l=pr[l];
        if (a[l+1]==b[i])
            l++;
        if (l==a.size ()-1)
            return 1;
    }
    return 0;
}
int pref (string &a)
{
    int l=0;
    pr[1]=0;
    for (int i=2; i<a.size (); i++)
    {
        while (l>0&&a[i]!=a[l+1])
            l=pr[l];
        if (a[i]==a[l+1])
            l++;
        pr[i]=l;
    }
    return l;
}
int main ()
{
    fin>>n;
    for (i=0; i<n; i++)
    {
        fin>>sir;
        s[i]="0";
        s[i]+=sir;
    }
    nr=0;
    for (i=0; i<n; i++)
    {
        ok=1;
        for (j=0; j<n; j++)
        {
            if (i==j)
                continue;
            if (match (s[i],s[j]))
            {
                ok=0;
                break;
            }
        }
        if (ok==1)
            s[nr++]=s[i];
    }
    n=nr;
    for (i=0; i<n; i++)
    {
        for (j=0; j<n; j++)
        {
            if (i==j)
                continue;
            ss=s[j]+"1"+s[i];
            l[i][j]=(s[j].size ()-1)-pref (ss);
        }
    }
    for (p=0; p<(1<<n); p++)
    {
        for (i=0; i<n; i++)
            dp[p][i]=inf;
    }
    for (i=0; i<n; i++)
    {
        dp[(1<<i)][i]=s[i].size ();
        t[(1<<i)][i]=-1;
    }
    for (p=1; p<(1<<n); p++)
    {
        for (i=0; i<n; i++)
        {
            if (!((p>>i)&1)||dp[p][i]!=inf)
                continue;
            nr=p-(1<<i);
            for (j=0; j<n; j++)
            {
                if (!((nr>>j)&1))
                    continue;
                if (dp[nr][j]+l[j][i]<dp[p][i])
                {
                    dp[p][i]=dp[nr][j]+l[j][i];
                    t[p][i]=j;
                }
            }
        }
    }
    minim=inf;
    for (i=0; i<n; i++)
    {
        if (dp[(1<<n)-1][i]<minim)
        {
            minim=dp[(1<<n)-1][i];
            poz=i;
        }
    }
    f (poz,(1<<n)-1);
    return 0;
}