Cod sursa(job #1108176)

Utilizator Theorytheo .c Theory Data 15 februarie 2014 14:28:56
Problema ADN Scor 20
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];

int F[1 << NMAX][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] = true; 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;
                F[state][last] = 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 print(int state, int last, int cnt) {

    if(cnt == nr - 1) return ;
    int fath = ind[F[state][last]];
    int son = ind[last];
    print(state ^ (1 << last), F[state][last], cnt + 1);


    for(int i = 1; i <= len[fath] - cost[fath][son];++i)
        fout << s[fath][i];
    if(cnt == 0)
        fout << s[son] + 1;
}


void solve() {

    build_graph();
    int sol = INF;

    init(); int ret;

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

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

        if(value < sol) {
            ret = i;
        }
    }

   print((1 << nr) - 1, ret, 0);



}

int main() {

    read();

    solve();

    return 0;
}