Cod sursa(job #2511347)

Utilizator david.teacaDavid Stefan Teaca david.teaca Data 18 decembrie 2019 20:48:12
Problema ADN Scor 70
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.58 kb
#include <bits/stdc++.h>
 
using namespace std;
 
ifstream in("adn.in");
ofstream out("adn.out");
 
const int DIM = 30017;
 
struct Sir
{
    int l;
    string s;
    int prefix[DIM];
 
    void add(string p)
    {
        memset(prefix, 0, sizeof(prefix));
 
        l = p.size();
        s = ' ' + p;
 
        int k = 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];
Sir t[20];
 
bool cmp(Sir a, Sir b)
{
    return (a.l < b.l);
}
 
int n;
 
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]);
}
 
void del()
{
    int k = 0;
 
    for(int i = 0; i < n; i++)
    {
        bool ok = false;
 
        for(int j = i + 1; j < n; j++)
            if(v[i].este(v[j]))
            {
                ok = true;
                break;
            }
 
        if(ok == false)
            t[k++] = v[i];
    }
 
    n = k;
}
 
int c[20][20];
 
void getCosts()
{
    for(int i = 0; i < n; i++)
        for(int j = 0; j < n; j++)
            if(i != j)
                c[j][i] = t[i].cost(t[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++)
        dp[(1 << i)][i] = t[i].l;
 
    for(int i = 0; i < (1 << n); 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 all = (1 << n) - 1;
 
    int start = 0;
 
    for(int i = 1; i < n; i++)
        if(dp[all][i] < dp[all][start])
            start = 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());
 
    t[path[0]].print(t[path[0]].l);
 
    for(int i = 1; i < path.size(); i++)
        t[path[i]].print(c[path[i - 1]][path[i]]);
}
 
main()
{
    read();
    del();
    getCosts();
    calcAns();
    printAns();
}