Cod sursa(job #2292594)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 29 noiembrie 2018 18:48:33
Problema ADN Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.29 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(const string &needle, const 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(const string &l, const 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;



        vector<vector<int>> dp((1 << n), vector<int> (n, -1));
        vector<vector<int>> boss((1 << n), vector<int> (n));

        for(int start = 0; start < n; start ++) {
            dp[1 << start][start] = 0;
            boss[1 << start][start] = start;
        }

        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][i] + cost[i][j] > dp[mask ^ (1 << j)][j]) {

                            dp[mask ^ (1 << j)][j] = dp[mask][i] + cost[i][j];
                            boss[mask ^ (1 << j)][j] = boss[mask][i];
                        }



        for(int i = 0; i < n; i ++) {

            if(mx < dp[(1 << n) - 1][i]) {

                x = boss[(1 << n) - 1][i];

                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;

}