Cod sursa(job #1108054)

Utilizator Theorytheo .c Theory Data 15 februarie 2014 12:54:07
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.01 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <cstdio>

using namespace std;

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

const int NMAX = 19;
const int LMAX = 30010;
const int INF = (1 << 30);

int N; char s[NMAX][LMAX]; int len[NMAX];

int cost[NMAX][NMAX]; int D[1 << NMAX][NMAX]; int previous[LMAX]; bool used[NMAX];

int nr; int ind[NMAX];int father[NMAX]; int father_min[NMAX]; int start; int inv[NMAX];

void read() {

    fin >> N;
    for(int i = 1; i <= N; ++i) {
        fin.get();
        fin.get(s[i] + 1, LMAX, '\n');
        len[i] = strlen(s[i] + 1);
    }
}

int kmp(int x, int y) {

    for(int i = 0 ;i <= len[x]; ++i)
        previous[i] = 0;
    int k = 0;

    for(int i = 2; i <= len[x]; ++i) {

        while(k > 0 && s[x][i] != s[x][k + 1]) k = previous[k];

        if(s[x][i] == s[x][k + 1]) ++k;

        previous[i] = k;
    }

    k = 0;

    for(int i = 1; i <= len[y]; ++i) {

        while(k > 0 && s[y][i] != s[x][k + 1]) k = previous[k];

        if(s[y][i] == s[x][k + 1]) ++k;

        if(k == len[x]) { used[x] = -1; return -1;}

    }

    return k;
}

void build_graph() {


    for(int i = 1; i < N; ++i) {
            if(used[i]) continue;
        for(int j = i + 1; j <= N; ++j) {

            if(used[j]) continue;
            int x = kmp(i, j); if(x == -1) break;
            int y = kmp(j, i);

            cost[j][i] = x; cost[i][j] = y;
        }
    }

    for(int i = 1; i <= N; ++i)
        if(!used[i]) {
            ind[nr] = i;
            ++nr;
    }
}

int compute(int state, int last, const int &initial) {

    if(D[state][last] != INF) return D[state][last];

    for(int i = 0 ;i < nr; ++i) {
        if(state & (1 << i)) {

            if(i == last || i == initial) continue;

            int v = compute(state ^ (1 << last), i, initial) - cost[ind[i]][ind[last]] + len[ind[last]];

            if(D[state][last] > v) {

                D[state][last] = v;
                father[ind[last]] = ind[i];
            }
        }
    }
    return D[state][last];
}

void init() {

   for(int i = 0 ; i < (1 << nr); ++i)
        for(int j = 0 ; j < nr; ++j)
            D[i][j] = INF;

    for(int i = 0; i < nr; ++i) {
        D[1 << i][i] = len[ind[i]];
    }
}


void solve() {

    build_graph();
    int sol = INF;

    init();

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

        int value = compute( (1 << nr) - 1 , i , i);

        if(value < sol) {
            for(int j = 1; j <= N; ++j)
                father_min[j] = father[j];
            sol = value;
            start = ind[i];
        }
    }


    for(int x = start, ct = 0; ct < nr; ct++, x = father_min[x]) {
        inv[nr - ct] = x;
    }
    for(int x = 1; x < nr; x++) {
        for(int i = 1; i <= len[inv[x]] - cost[inv[x]][inv[x + 1]]; ++i)
            fout << s[inv[x]][i];
    }
    fout << s[start] + 1 ;



}

int main() {

    read();

    solve();

    return 0;
}