Cod sursa(job #3201310)

Utilizator PowerPlantNICOLAS ANDREI MANASIA PowerPlant Data 7 februarie 2024 16:04:22
Problema ADN Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.91 kb
#include <bits/stdc++.h>
#define int long long

using namespace std;
ifstream fin ("adn.in");
ofstream fout ("adn.out");

bool v[20];
string s[20];
string S;
vector <int> V, A;
int C[20][20], pi[60030], prec[20][(1 << 20) + 10];
long long dp[20][(1 << 20) + 10];
int n;

void DFS(int node, int config)
{
    for(auto it : V)
        if(( (1 << it) & config) == 0 && dp[it][config + (1 << it)] < dp[node][config] + C[node][it])
        {
            dp[it][config + (1 << it)] = dp[node][config] + C[node][it];
            prec[it][config + (1 << it)] = node;
            DFS(it, config + (1 << it));
        }
}


signed main()
{
    fin >> n;
    for(int i = 1; i <= n; ++i)
        fin >> s[i];


    for(int i = 1; i < n; ++i)
        for(int j = i + 1; j <= n; ++j)
        {
            int x, y;
            if(s[i].size() <= s[j].size())
                x = i, y = j;
            else x = j, y = i;

            string S1 = "~" + s[x] + "~";
            string S2 = "~" + s[y];
            int k = 0;
            pi[1] = 0;
            for(int e = 2; e < S1.size() - 1; ++e)
            {
                while(k != 0 && S1[k + 1] != S1[e])
                    k = pi[k];
                if(S1[k + 1] == S1[e])
                    ++k;
                pi[e] = k;
            }

            k = 0;
            for(int e = 1; e < S2.size(); ++e)
            {
                while(k != 0 && S1[k + 1] != S2[e])
                    k = pi[k];
                if(S1[k + 1] == S2[e])
                    ++k;
                if(k == S1.size() - 2)
                    v[x] = 1;
            }


        }
    long long conf = 0;
    for(int i = 1; i <= n; ++i)
        if(v[i] == 0)
            V.push_back(i), conf = conf + (1 << i);

    for(auto i : V)
        for(auto j : V)
            if(i != j)
            {
                S = "@" + s[i] + "$" + s[j] + "=";
                int k = 0;
                pi[1] = 0;
                for(int e = 2; e < S.size() - 1; ++e)
                {
                    while(k != 0 && S[k + 1] != S[e])
                        k = pi[k];
                    if(S[k + 1] == S[e])
                        ++k;
                    pi[e] = k;
                }
                C[j][i] = pi[S.size() - 2];
            }

    for(auto i : V)
        DFS(i, (1 << i));
    long long ans = 0;
    int poz = 0;
    for(auto i : V){
        if(ans < dp[i][conf]) poz = i;
        ans = max(ans, dp[i][conf]);
    }
    A.push_back(poz);

    while(conf != 0)
    {
        int aux = prec[poz][conf];
        conf -= (1 << poz);
        poz = aux;
        if(conf != 0) A.push_back(poz);
    }

    for(int i = A.size() - 1; i > 0; --i)
        for(int j = 0; j <= s[A[i]].size() - 1 - C[A[i]][A[i - 1]]; ++j)
            fout << s[A[i]][j];
    for(int j = 0; j <= s[A[0]].size(); ++j)
        fout << s[A[0]][j];
    return 0;
}