Cod sursa(job #1169649)

Utilizator mihai995mihai995 mihai995 Data 11 aprilie 2014 20:04:10
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.27 kb
#include <fstream>
#include <iostream>
#include <cstring>
using namespace std;

const int N = 18, L = 30001, inf = 0x3f3f3f3f;

char sir[N][L];
int best[1 << N][N], cost[N][N], pi[L], n;

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

int getCost(char a[], char b[]){
    int sizeB = strlen(b + 1);

    pi[0] = -1; pi[1] = 0;
    for (int i = 1 ; b[i] ; i++){
        pi[i] = pi[i - 1];
        while ( pi[i] >= 0 && b[ pi[i] + 1 ] != b[i] )
            pi[i] = pi[ pi[i] ];
        pi[i]++;
    }

    int k = 0;
    for (int i = 1 ; k != sizeB && a[i] ; i++){
        while ( k >= 0 && b[k + 1] != a[i] )
            k = pi[k];
        k++;
    }

    return sizeB - k;
}

inline int getCost(int x, int y){
    return getCost(sir[x], sir[y]);
}

inline bool valid(int mask, int x, int y){
    return x != y && ( mask & (1 << x) ) && ( mask & (1 << y) );
}

bool isRelevant(int x){
    int poz = 0;
    while (poz < n && (poz == x || getCost(poz, x) != 0))
        poz++;
    return poz == n;
}

void print(int mask, int k){
    int p = 0;
    while ( p < n && ( p == k || ( mask & (1 << p) ) == 0 || best[mask][k] != best[mask ^ (1 << k)][p] + cost[p][k] ) )
        p++;
    if (p != n){
        print(mask ^ (1 << k), p);
        out << (sir[k] + strlen(sir[k] + 1) + 1 - cost[p][k]);
    } else
        out << sir[k] + 1;
}

int main(){
    in >> n;
    for (int i = 0 ; i < n ; i++)
        in >> (sir[i] + 1);

    int nr = 0;
    for (int i = 0 ; i < n ; i++)
        if ( isRelevant(i) )
            strcpy(sir[nr++] + 1, sir[i] + 1);
    n = nr;

    memset(best, inf, sizeof(best));
    for (int i = 0 ; i < n ; i++)
        best[1 << i][i] = strlen( sir[i] + 1 );

    for (int i = 0 ; i < n ; i++)
        for (int j = 0 ; j < n ; j++)
            cost[i][j] = getCost(i, j);

    for (int i = 0 ; i < (1 << i) ; i++)
        for (int j = 0 ; j < n ; j++)
            for (int k = 0 ; k < n ; k++)
                if ( valid(i, j, k) )
                    best[i][j] = min(best[i][j], best[i ^ (1 << j)][k] + cost[k][j]);
    int k = 0, mask = (1 << n) - 1;
    for (int i = 1 ; i < n ; i++)
        if ( best[mask][i] < best[mask][k] )
            k = i;

    print(mask, k);
    out << '\n';

    return 0;
}