Cod sursa(job #1750169)

Utilizator akaprosAna Kapros akapros Data 29 august 2016 17:53:03
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.21 kb
#include <bits/stdc++.h>
#define maxN 21
#define maxP (1 << 19) + 1
#define maxL 30005
#define inf 1000000000
using namespace std;
int n, m, all, ans, cost[maxN][maxN], dp[maxN][maxP + 1], len[maxN];
int v[maxL], path[maxN], p[maxN];
char s[maxN][maxL];
bool u[maxN];
void pref(int x)
{
    memset(v, 0, sizeof(v));
    v[1] = 0;
    int i, k = 0;
    for (i = 2; i <= len[x]; ++ i)
    {
        while (k > 0 && s[x][i]!= s[x][k + 1])
            k = v[k];
        if (s[x][i] == s[x][k + 1])
            ++ k;
        v[i] = k;
    }
}
void read()
{
    int i;
    freopen("adn.in", "r", stdin);
    scanf("%d\n", &n);
    for (i = 0; i < n; ++ i)
    {
        scanf("%s\n", s[i] + 1);
        len[i] = strlen(s[i] + 1);
    }
}
void init()
{
    int i, j;
    n = m;
    all = (1 << n) - 1;
    for (i = 0; i < n; ++ i)
        for (j = 0; j <= all; ++ j)
            dp[i][j] = inf;
    dp[0][1] = 0;
    ans = inf;
}
void get_cost()
{
    int x, y;
    for (x = 0; x < n; ++ x)
        for (y = 0; y < n; ++ y)
            if (x != y)
            {
                cost[y][x] = -1;
                pref(y);
                int i, k = 0, c;
                for (i = 1; i <= len[x]; ++ i)
                {
                    while (k > 0 && s[x][i] != s[y][k + 1])
                        k = v[k];
                    if (s[x][i] == s[y][k + 1])
                        ++ k;
                    if (k == len[y])
                    {
                        cost[y][x] = 0;
                        u[y] = 1;
                        break;
                    }
                    if (i == len[x] && cost[y][x])
                    cost[y][x] = len[y] - k;
                }
            }
        for (y = 0; y < n; ++ y)
        if (!u[y])
            p[m ++] = y;
}
void solve()
{
    get_cost();

    init();

    int i, j, b;
    for (i = 1; i <= all; ++ i)
        if ((i & (i - 1)) == 0)
        for (j = 0; j < n; ++ j)
            if (i & (1 << j))
               dp[j][i] = len[p[j]];

    for (i = 1; i <= all; ++ i)
    for (j = 0; j < n; ++ j)
    if (i & (1 << j))
        {
            for (b = 0; b < n; ++ b)
            if (!(i & (1 << b)) && dp[b][i ^ (1 << b)] > dp[j][i] + cost[p[b]][p[j]])
               dp[b][i ^ (1 << b)] = dp[j][i] + cost[p[b]][p[j]];
            if (i == all && dp[j][i] < ans)
            {
                ans = dp[j][i];
                path[0] = j;
            }
        }
    i = 0;
    while (i < n - 1)
    {
        int j;
        for (j = 0; j < n; ++ j)
            if (dp[path[i]][all] == dp[j][all ^ (1 << path[i])] + cost[p[path[i]]][p[j]])
            {
                all ^= (1 << path[i]);
                path[++ i] = j;
                break;
            }
    }
}
void write()
{
    int i, j, q = 1;
    freopen("adn.out", "w", stdout);
    //printf("%d\n", ans);
    for (j = m - 1; j >= 0; -- j)
    {
        for (i = q; i <= len[p[path[j]]]; ++ i)
                printf("%c", s[p[path[j]]][i]);

        if (j)
        q = len[p[path[j - 1]]] - cost[p[path[j - 1]]][p[path[j]]] + 1;
    }
    printf("\n");
}
int main()
{
    read();
    solve();
    write();
    return 0;
}