Cod sursa(job #1492537)

Utilizator cojocarugabiReality cojocarugabi Data 27 septembrie 2015 21:01:59
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
# include <bits/stdc++.h>
using namespace std;
ifstream fi("adn.in");
ofstream fo("adn.out");
char v[22][33333];
int phi[33333];
int s[22][22];
int dp[1 << 18][18];
int fr[1 << 18][18];
int len[22];
int main(void)
{
    int n;
    fi>>n;
    for (int i = 0;i < n;++i) fi>>(v[i] + 1),len[i] = strlen(v[i] + 1);
    int mask = 1 << n;--mask;
    for (int i = 0;i < n;++i)
    {
        int k = 0;
        for (int j = 2;j <= len[i];++j)
        {
            while (k && v[i][j] != v[i][k+1]) k = phi[k];
            k += v[i][j] == v[i][k+1];
            phi[j] = k;
        }
        for (int p = 0;p < n;++p)
            if (i != p)
            {
                k = 0;
                for (int j = 1;j <= len[p];++j)
                {
                    while (k && v[p][j] != v[i][k+1]) k = phi[k];
                    k += v[p][j] == v[i][k+1];
                    if (k == len[i])
                    {
                        mask &= mask ^ (1 << i);
                        k = phi[k];
                    }
                }
                s[p][i] = len[i] - k;
            }
    }
    int cnt = 1 << n;
    for (int bit = 1;bit < cnt;++bit)
        for (int j = 0;j < n;++j)
            if ((bit >> j)&1)
                dp[bit][j] = 2e9,fr[bit][j] = -1;
    for (int i = 0;i < n;++i) dp[1 << i][i] = len[i];
    for (int bit = 0;bit < cnt;++bit)
    {
        for (int i = 0;i < n;++i)
            if ((bit >> i)&1)
                for (int j = 0;j < n;++j)
                    if (!((bit >> j)&1))
                        if (dp[bit^(1<<j)][j] > dp[bit][i] + s[i][j])
                        {
                            dp[bit^(1<<j)][j] = dp[bit][i] + s[i][j];
                            fr[bit^(1<<j)][j] = i;
                        }
    }
    cnt = mask;
    int pos = -1;
    int mn = 2e9;
    for (int i = 0;i < n;++i)
        if (mn > dp[cnt][i] && ((cnt >> i) & 1))
            mn = dp[cnt][i],pos = i;
    vector < int > ans;
    while (pos != -1)
    {
        ans.push_back(pos);
        cnt ^= 1 << pos;
        pos = fr[cnt | (1 << pos)][pos];
    }
    int siz = 0;
    for (int i = 0;i < n;++i) siz += (mask >> i) & 1;
    reverse(ans.begin(),ans.begin()+siz);
    fo << (v[ans[0]] + 1);
    for (int i = 1;i < siz;++i)
    {
        int l = s[ans[i-1]][ans[i]];
        for (int j = len[ans[i]] - l + 1;j <= len[ans[i]];++j)
            fo << v[ans[i]][j];
    }
    return fo << '\n',0;
}