Cod sursa(job #2285700)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 18 noiembrie 2018 23:08:09
Problema ADN Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.74 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>

using namespace std;

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

inline bool isincluded(string needle, string haystack) {
    vector<int> pi(needle.size(), 0);
    int k = 0;
    for(int i = 2; i < needle.size(); i ++) {
        while(k > 0 && needle[i] != needle[k + 1])
            k = pi[k];
        if(needle[k + 1] == needle[i])
            k ++;
        pi[i] = k;
    }

    k = 0;
    for(int i = 1; i < haystack.size(); i ++) {
        while(k > 0 && haystack[i] != needle[k + 1])
            k = pi[k];
        if(haystack[i] == needle[k + 1])
            k ++;
        if(k == needle.size() - 1)
            return 1;
    }

    return 0;
}

inline int computekmp(string l, string r) {
    string s = l + r;
    vector<int> pi(s.size(), 0);

    int k = 0;
    for(int i = 2; i < s.size(); i ++) {
        while(k > 0 && s[i] != s[k + 1])
            k = pi[k];
        if(s[i] == s[k + 1])
            k ++;
        pi[i] = k;
    }

    return pi[s.size() - 1];
}

int main() {
    int n;
    in >> n;
    vector<string> v(n + 1);
    for(int i = 1; i <= n; i ++) {
        in >> v[i];
        v[i] = " " + v[i];
    }

    vector<string> words;
    for(int i = 1; i <= n; i ++) {
        bool flag = 0;
        for(int j = 1; j <= n; j ++)
            if(i != j && isincluded(v[i], v[j])) {
                flag = 1;
                break;
            }
        if(!flag)
            words.push_back(v[i]);
    }

    //trag muchii
    n = words.size();
    vector<vector<int> > cost(n, vector<int> (n, -1));
    for(int i = 0; i < n; i ++)
        for(int j = 0; j < n; j ++)
            if(i != j)
                cost[j][i] = computekmp(words[i], words[j]);

    //caut lantul hamiltonian de cost maxim
    int mx = -1, x, y;

    for(int start = 0; start < n; start ++) {
        vector<vector<int> > dp((1 << n), vector<int> (n, -1));

        dp[1 << start][start] = 0;
        for(int mask = 1; mask < (1 << n); mask ++)
            for(int i = 0; i < n; i ++)
                if(mask & (1 << i) && dp[mask][i] != -1)
                    for(int j = 0; j < n; j ++)
                        if((mask & (1 << j)) == 0)
                            dp[mask ^ (1 << j)][j] = max(dp[mask ^ (1 << j)][j], dp[mask][i] + cost[i][j]);

        for(int i = 0; i < n; i ++) {
            if(mx < dp[(1 << n) - 1][i]) {
                x = start;
                y = i;
                mx = dp[(1 << n) - 1][i];
            }
        }
    }

    vector<vector<int> > rdp((1 << n), vector<int> (n, -1));
    vector<vector<int> > from((1 << n), vector<int> (n, -1));

    int start = x;
    rdp[1 << start][start] = 0;
    for(int mask = 1; mask < (1 << n); mask ++)
        for(int i = 0; i < n; i ++)
            if(mask & (1 << i) && rdp[mask][i] != -1)
                for(int j = 0; j < n; j ++)
                    if((mask & (1 << j)) == 0)
                        if(rdp[mask ^ (1 << j)][j] < rdp[mask][i] + cost[i][j]) {
                           rdp[mask ^ (1 << j)][j] = rdp[mask][i] + cost[i][j];
                           from[mask ^ (1 << j)][j] = i;
                        }

    int node = y, nr = n - 1, mask = (1 << n) - 1;
    vector<int> ans(n, 0);
    while(node != -1) {
        ans[nr --] = node;
        int cnode = node;
        node = from[mask][node];
        mask ^= (1 << cnode);
    }

    int toskip = 1;
    for(int i = 0; i < n; i ++) {
        for(int j = toskip; j < words[ans[i]].size(); j ++)
            out << words[ans[i]][j];
        if(i + 1 < n)
            toskip = cost[ans[i]][ans[i + 1]] + 1;
    }

    return 0;
}