Cod sursa(job #2459505)

Utilizator Briana_NeaguNeagu Briana Briana_Neagu Data 22 septembrie 2019 12:59:49
Problema ADN Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <bits/stdc++.h>
#define nmax 19
#define lmax 30019
#define inf (1 << 30)
using namespace std;

ifstream f("adn.in");
ofstream g("adn.out");


string s[nmax];
int leng[nmax];
const int B = 197;
unsigned long long h[nmax][lmax], bpow[lmax];
int remain[nmax][nmax];
vector <int> sir;
bool pa[nmax];
int rez[1 << nmax][nmax];
int dp[1 << nmax][nmax];

bool duplicates(int a, int b)
{
    unsigned long long  hash = h[a][leng[a] - 1];
    for (int i = 1; i + leng[a]  - 1 < leng[b]; ++ i)
        if (hash ==( h[b][i + leng[a] - 1] - h[b][i - 1] * bpow[leng[a]]))
        {
            pa[a] = 1;
            return true;
        }
    return false;
}

void show_solution(int mask, int seed)
{
    int prev = rez[mask][seed];
    if (prev == -1)
    {
        g << s[sir[seed]];
        return;
    }
    show_solution(mask ^ (1 << seed), prev);
    for (int i = leng[sir[seed]] - remain[sir[prev]][sir[seed]]; i < leng[sir[seed]]; ++ i)
        g << s[sir[seed]][i];
}

void make_hash(string s, int id)
{
    h[id][0] = (int)s[0];
    int len = s.length();
    for (int i = 1; i < len; ++ i)
        h[id][i] = h[id][i - 1] * B + s[i];
    leng[id] = len;
}

int main()
{
    int n;
    f >> n;
    for (int i = 0; i < n; ++ i)
    {
        f >> s[i];
        make_hash(s[i], i);
    }
    bpow[0] = 1;
    for (int i = 1; i < lmax; ++ i)
        bpow[i] = bpow [i - 1] * B;
    for (int i = 0; i < n; ++ i)
        for (int j = 0; j < n; ++ j)
        {
            if (i == j || pa[i] || pa[j])
                continue;

            int a = i, b = j;
            if (leng[i] > leng[j])
                swap(a, b);
            if (duplicates(a, b))
                continue;
            for (int k = leng[a]; k >= 0; -- k)
                if (h[i][leng[i] - 1] - h[i][leng[i] - 1 - k] * bpow[k] == h[j][k - 1])
                {
                    if (k == leng[a])
                    {
                        pa[a] = 1;
                    }
                    remain[i][j] = leng[j] - k;
                    break;
                }
        }
    for (int i = 0; i < n; ++ i)
        if (!pa[i])
            sir.push_back(i);

    n = sir.size();
    for (int i = 0; i < n; ++ i)
    {
        dp[1 << i][i] = leng[sir[i]];
        rez[1 << i][i] = -1;
    }
    for (int mask = 1; mask < (1 << n); ++ mask)
        for (int last = 0; last < n; ++ last)
            if (mask & (1 << last))
                for (int now = 0; now < n; ++ now)
                    if (!(mask & (1 << now)))
                        if (dp[mask | (1 << now)][now] == 0 || dp[mask | (1 << now)][now] > dp[mask][last] + remain[sir[last]][sir[now]])
                        {
                            dp[mask | (1 << now)][now] =  dp[mask][last] + remain[sir[last]][sir[now]];
                            rez[mask | (1 << now)][now] = last;
                        }
    int ans = inf;
    int seed;
    for (int i = 0; i < n; ++ i)
        if (ans > dp[(1 << n) - 1][i])
        {
            ans = dp[(1 << n) - 1][i];
            seed = i;
        }
    show_solution((1 << n) - 1, seed);
}