Cod sursa(job #2292572)

Utilizator caesar2001Stoica Alexandru caesar2001 Data 29 noiembrie 2018 18:24:22
Problema ADN Scor 90
Compilator cpp-32 Status done
Runda Arhiva de probleme Marime 4.04 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;



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

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



        dp[start][1 << start] = 0;

        for(int mask = 1; mask < (1 << n); mask ++)

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

                if(mask & (1 << i) && dp[i][mask] != -1)

                    for(int j = 0; j < n; j ++)

                        if((mask & (1 << j)) == 0)

                            dp[j][mask ^ (1 << j)] = max(dp[j][mask ^ (1 << j)], dp[i][mask] + cost[i][j]);



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

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

                x = start;

                y = i;

                mx = dp[i][(1 << n) - 1];

            }

        }

    }



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

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



    int start = x;

    rdp[start][1 << start] = 0;

    for(int mask = 1; mask < (1 << n); mask ++)

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

            if(mask & (1 << i) && rdp[i][mask] != -1)

                for(int j = 0; j < n; j ++)

                    if((mask & (1 << j)) == 0)

                        if(rdp[j][mask ^ (1 << j)] < rdp[i][mask] + cost[i][j]) {

                           rdp[j][mask ^ (1 << j)] = rdp[i][mask] + cost[i][j];

                           from[j][mask ^ (1 << 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[node][mask];

        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;

}