Cod sursa(job #2801020)

Utilizator UnknownPercentageBuca Mihnea-Vicentiu UnknownPercentage Data 14 noiembrie 2021 18:15:49
Problema ADN Scor 20
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.8 kb
#include <bits/stdc++.h>

using namespace std;

inline void Open(const string Name) {
    #ifndef ONLINE_JUDGE
        (void)!freopen((Name + ".in").c_str(), "r", stdin);
        (void)!freopen((Name + ".out").c_str(), "w", stdout);
    #endif
}

using vva = vector <vector <array <int, 2>>>;
using vv = vector <vector <int>>;
using v = vector <string>;


void printSTR(v vec, vv ccc, vva path, array <int, 2> cur) {
    if(cur[0] == 0)
        return;

    printSTR(vec, ccc, path, path[cur[0]][cur[1]]);
    int cost = ccc[path[cur[0]][cur[1]][1]][cur[1]];
    if(path[cur[0]][cur[1]][0] == 0) 
        cost = 0;

    cout << vec[cur[1]].substr(cost);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    const int INF = 1e9;

    auto KMP = [](string str1, string str2) {
        str1 = ' ' + str1;
        str2 = ' ' + str2;

        int len = str1.size() - 1, lenn = str2.size() - 1, q = 0;
        vector <int> pi(len + 1);
        for(int i = 2;i <= len;i++) {
            while(q && str1[q + 1] != str1[i]) 
                q = pi[q];
            if(str1[q + 1] == str1[i])
                q++;

            pi[i] = q;
        }

        q = 0;
        for(int i = 1;i <= lenn;i++)  {
            while(q && str1[q + 1] != str2[i])
                q = pi[q];
            if(str1[q + 1] == str2[i])
                q++;
            if(q == len)
                return 1;
        }
        return 0;
    };

    auto LenPS = [](string str1, string str2) {
        string str = "2" + str2 + "2" +  str1;

        int len = str.size(), q = 0;
        vector <int> pi(len);

        //pi[1] = 0;
        for(int i = 2;i < len;i++) {
            while(q && str[q + 1] != str[i])
                q = pi[q];
            if(str[q + 1] == str[i])
                q++;
            pi[i] = q; 
        }

        return pi.back();
    };

    auto cmp = [](string str1, string str2) {
        return str1.size() < str2.size();
    };

    Open("adn");

    int N; cin >> N;
    vector <string> v(N);
    for(string &x : v)
        cin >> x;

    sort(v.begin(), v.end(), cmp);
    vector <bool> marked(N);
    for(int i = 0;i < N - 1;i++)
        for(int j = i + 1;j < N;j++)
            if(KMP(v[i], v[j]) == 1) {
                marked[i] = 1;
                break;
            }

    for(int i = 0, cnt = 0;i < N;i++) {
        if(marked[i]) {
            v.erase(v.begin() + i - cnt);
            cnt++;
        }
    }

    N = v.size();
    vector <vector <array <int, 2>>> Gr(N);
    vector <vector <int>> cost(N, vector <int>(N));
    for(int i = 0;i < N;i++)
        for(int j = 0;j < N;j++)  
            if(i != j) {
                int val = LenPS(v[i], v[j]);
                Gr[j].push_back({i, val});
                cost[i][j] = val;
            }

    int limit = 1 << N;
    vector <vector <int>> dp(limit, vector <int>(N, -INF));
    vector <vector <array <int, 2>>> path(limit, vector <array <int, 2>>(N));

    for(int i = 0;i < N;i++)
        dp[1 << i][i] = 0;

    for(int i = 0;i < limit;i++)
        for(int j = 0;j < limit;j++) {
            if((i & (1 << j)) == 0)
                continue;

            for(array <int, 2> it : Gr[j]) {
                if((i & (1 << it[0])) == 0)
                    continue;

                if(dp[i ^ (1 << j)][it[0]] + it[1] > dp[i][j]) {
                    dp[i][j] = dp[i ^ (1 << j)][it[0]] + it[1];
                    path[i][j] = {i ^ (1 << j), it[0]};
                }

            }
        }

    int ans = -INF;
    array <int, 2> ppp;

    for(int i = 0;i < N;i++){
        if(dp[limit - 1][i] > ans) {
            ans = dp[limit - 1][i];
            ppp = {limit - 1, i};
        }
    }

    printSTR(v, cost, path, ppp);

    return 0;
}