Cod sursa(job #926434)

Utilizator vendettaSalajan Razvan vendetta Data 25 martie 2013 10:56:04
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.77 kb
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>

using namespace std;

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

#define nmax 19
#define Smax 30005
#define inf (1<<30)

int n, pi[Smax];
vector<string> v;
bool viz[nmax];
int dp[1<<nmax][nmax];
vector<int> v2;
int cnt = 0;
int mat[nmax][nmax];

void citeste(){
    f >> n;
    f.get(); string S;

    for(int i=1; i<=n; ++i){
        getline(f, S);
        v.push_back(S);
    }
}

void prefix(int poz){
    for(int i=0; i<Smax; ++i) pi[i] = 0;
    pi[0] = -1;
    for(int i=1, q=-1; i<v[poz].size(); ++i){
        while( q!=-1 && v[poz][q+1] != v[poz][i]) q = pi[q];
        if ( v[poz][q+1] == v[poz][i]) ++q;
        pi[i] = q;
    }
    //for(int i=0; i<v[poz].size(); ++i) cout << pi[i] << " ";
}

inline int kmp(int x, int y){
    // x pentru text; y = pentru pattern
    int q = -1;
    for(int i=0; i<v[x].size(); ++i){
        while( q!=-1 && v[y][q+1] != v[x][i]) q = pi[q];
        if (v[y][q+1] == v[x][i]) ++q;
        if (q+1 == v[y].size()) return q+1;
    }
    return q+1;
}

void elimina(){
    for(int i=0; i<n; ++i){
        if (viz[i] == 1) continue;
        prefix(i);
        for(int j=0; j<n; ++j){// vreau sa vad daca j il mananca pe i
            if (i == j) continue;
            if ( kmp(j, i) == v[i].size()){
                viz[i] = 1;// e eliminat
                break;
            }
        }
    }
    for(int i=0; i<n; ++i){
        if (viz[i] == 0)
            v2.push_back(i);
    }

}

void faDrum(int conf, int poz){
    int precConf = conf - (1<<poz);
    if (precConf == 0){
        for(int i=0; i<v[ v2[poz] ].size(); ++i) g << v[ v2[poz] ][i], ++cnt;
        return;
    }

    int newPoz = 0;
    int n2 = v2.size();
    for(int j=0; j<n2; ++j){
        if ( (precConf & (1<<j)) != 0){
            if (dp[precConf][j] + mat[j][poz] == dp[conf][poz]){
                newPoz = j;
                break;
            }
        }
    }
    faDrum(precConf, newPoz);

    for(int i=v[ v2[poz] ].size()-mat[newPoz][poz]; i<v[ v2[poz] ].size(); ++i){
        g << v[ v2[poz] ][i], ++cnt;
    }

}

void bagaMat(){
    int n2 = v2.size();
    for(int i=0; i<n2; ++i){
        for(int j=0; j<n2; ++j){
            if (j == i) continue;
            // j e dupa i
            prefix(v2[j]);
            mat[i][j] =  v[ v2[j] ].size() - kmp( v2[i], v2[j] );
        }
    }

}

void rezolva(){
    // elimin cuvintele care apare in altele
    // apoi bag o dinamica dp[i][j] = lungimea minima a cuvintelor corespunzatori bitilor de 1
    // din conf a. i. ultimul cuvant sa fie al j-lea
    // mat[i][j] = cat mai trebuie sa adaug daca il pun pe j dupa i;

    elimina();
    bagaMat();

    int n2 = v2.size();
    int lim = (1<<n2);
    for(int i=0; i<lim; ++i) for(int j=0; j<n2; ++j) dp[i][j] = inf;
    for(int i=0; i<n2; ++i) dp[1<<i][i] = v[ v2[i] ].size();

    for(int conf=3; conf<lim; ++conf){
        for(int j=0; j<n2; ++j){
            if ( (conf & (1<<j))!=0 ){// j e 1
                int precConf = conf - (1<<j);
                if (precConf == 0) continue;
                for(int k=0; k<n2; ++k){
                    if ( ( precConf &(1<<k) ) !=0 ){// dupa k il pun pe j
                        int pozJ = v2[j]; int pozK = v2[k];
                        dp[conf][j] = min(dp[conf][j], dp[precConf][k] + mat[k][j]);
                    }
                }
            }
        }
    }

    int Min = inf; int Poz = 0;
    for(int i=0; i<n2; ++i){
        if (dp[lim-1][i] < Min){
            Min = dp[lim-1][i];
            Poz = i;
        }
    }

    faDrum(lim-1, Poz);
}

int main(){
    citeste();
    rezolva();

    f.close();
    g.close();

    return 0;
}