Cod sursa(job #2433932)

Utilizator mihai50000Mihai-Cristian Popescu mihai50000 Data 29 iunie 2019 19:48:46
Problema ADN Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.64 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 300017;

struct Sir
{
    int l;
    string s;
    int prefix[DIM];

    void add(string p)
    {
        l = p.size();
        s = ' ' + p;

        int k = 0;

        for(int i = 0; i <= l; i++)
            prefix[i] = 0;

        for(int i = 2; i <= l; i++)
        {
            while(k != 0 && s[k + 1] != s[i])
                k = prefix[k];

            if(p[k + 1] == s[i])
                k++;

            prefix[i] = k;
        }
    }

    bool este(Sir x)
    {
        int k = 0;

        for(int i = 1; i <= x.l; i++)
        {
            while(k != 0 && s[k + 1] != x.s[i])
                k = prefix[k];

            if(s[k + 1] == x.s[i])
                k++;

            if(k == l)
                return true;
        }

        return false;
    }

    int cost(Sir x)
    {
        int k = 0;

        for(int i = 1; i <= x.l; i++)
        {
            while(k != 0 && s[k + 1] != x.s[i])
                k = prefix[k];

            if(s[k + 1] == x.s[i])
                k++;
        }

        return l - k;
    }

    void print(int nr)
    {
        for(int i = l - nr + 1; i <= l; i++)
            out << s[i];
    }
};

Sir v[20];

bool cmp(Sir a, Sir b)
{
    return (a.l < b.l);
}

int n;
int all;

void read()
{
    in >> n;

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

        in >> temp;

        v[i].add(temp);
    }

    for(int i = 0; i < n - 1; i++)
        for(int j = i + 1; j < n; j++)
            if(v[i].l > v[j].l)
                swap(v[i], v[j]);

    all = (1 << n) - 1;
}

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

        for(int j = i + 1; j < n; j++)
            if(v[i].este(v[j]))
            {
                all ^= (1 << i);
                break;
            }
}

int c[20][20];

void getCosts()
{
    for(int i = 0; i < n; i++)
        if(all & (1 << i))
            for(int j = 0; j < n; j++)
                if(i != j && (all & (1 << j)))
                    c[j][i] = v[i].cost(v[j]);
}

int dp[(1 << 19)][19];
int from[(1 << 19)][19];

const int INF = 1e8;

void init()
{
    for(int i = 0; i < (1 << n); i++)
        for(int j = 0; j < n; j++)
            dp[i][j] = INF;
}

void calcAns()
{
    init();

    for(int i = 0; i < n; i++)
        if(all & (1 << i))
            dp[(1 << i)][i] = v[i].l;

    for(int i = 0; i < (1 << n); i++)
        if((i & all) == i)
            for(int j = 0; j < n; j++)
                if(i & (1 << j))
                    for(int k = 0; k < n; k++)
                        if(i & (1 << k))
                            if(dp[i][j] > dp[i ^ (1 << j)][k] + c[k][j])
                            {
                                dp[i][j] = dp[i ^ (1 << j)][k] + c[k][j];
                                from[i][j] = k;
                            }
}

void printAns()
{
    int best = INF;

    int start = -1;

    for(int i = 0; i < n; i++)
        if(all & (1 << i))
            if(dp[all][i] < best)
                start = i, best = dp[all][i];

    vector <int> path;

    int now = start;

    while(all > 0)
    {
        path.push_back(now);

        int urm = from[all][now];
        all ^= (1 << now);
        now = urm;
    }

    reverse(path.begin(), path.end());

    v[path[0]].print(v[path[0]].l);

    for(int i = 1; i < path.size(); i++)
        v[path[i]].print(c[path[i - 1]][path[i]]);
}

main()
{
    read();
    del();
    getCosts();
    calcAns();
    printAns();
}