Cod sursa(job #2719283)

Utilizator CleliaClelia Maria Dobrescu Clelia Data 9 martie 2021 19:04:37
Problema ADN Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.11 kb
#include <fstream>
#include <cstring>
using namespace std;
ifstream fin ("adn.in");
ofstream fout ("adn.out");
int dp[(1<<18)][20],pre[(1<<18)][20],l[20],pi[20][30005],in[20],c[20][20];
char s[20][30005];
void prefix (int ind)
{
    int now=0,i;
    for (i=2;i<=l[ind];i++)
    {
        now=pi[ind][i-1];
        while (now && s[ind][i]!=s[ind][now+1])
            now=pi[ind][now];
        if (s[ind][i]==s[ind][now+1])
            now++;
        pi[ind][i]=now;
    }
}
int kmp (int x,int y)
{
    int now=0,i;
    for (i=1;i<=l[x];i++)
    {
        while (now && s[x][i]!=s[y][now+1])
            now=pi[y][now];
        if (s[x][i]==s[y][now+1])
            now++;
        if (now==l[y])
            return l[y];
    }
    return now;
}
void atrb (int i,int j)
{
    if (kmp(i,j)==l[j])
        in[j]=1;
    else
        c[i][j]=-kmp(i,j);
}
void recon (int mask,int p)
{
    if (mask==(1<<p))
    {
        fout<<s[p]+1;
        return;
    }
    recon(mask^(1<<p),pre[mask][p]);
    fout<<(s[p]+1-c[pre[mask][p]][p]);
}
int main()
{
    int n,f=0,i,j,ans=200000000,last,mask;
    fin>>n;
    for (i=0;i<n;i++)
        for (j=0;j<(1<<n);j++)
            dp[j][i]=200000000;
    for (i=0;i<n;i++)
    {
        fin>>(s[i]+1);
        l[i]=strlen(s[i]+1);
        prefix(i);
    }
    for (i=0;i<n;i++)
        for (j=i+1;j<n;j++)
        {
            atrb(i,j);
            atrb(j,i);
        }
    for (i=0;i<n;i++)
        if (!in[i])
        {
            f+=(1<<i);
            dp[(1<<i)][i]=0;
        }
    for (mask=1;mask<(1<<n);mask++)
        for (i=0;i<n;i++)
            if (mask&(1<<i) && !in[i])
                for (j=0;j<n;j++)
                    if (i!=j && !in[j] && mask&(1<<j) && dp[mask][i]>dp[mask^(1<<i)][j]+c[j][i])
                    {
                        dp[mask][i]=min(dp[mask][i],dp[mask^(1<<i)][j]+c[j][i]);
                        pre[mask][i]=j;
                    }
    for (i=0;i<n;i++)
        if (dp[f][i]<ans)
        {
            ans=dp[f][i];
            last=i;
        }
    recon(f,last);
    return 0;
}