Cod sursa(job #2313909)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 7 ianuarie 2019 17:00:41
Problema ADN Scor 30
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.33 kb
#include<fstream>
#include<cstring>
#define DIM 30005
using namespace std;
int n, i, ii, j, jj, L, x;
int d[(1 << 18) + 2][18], p[DIM], a[20][20], m[20], t[(1 << 18) + 2][18], ok[20];
char s[19][DIM];
ifstream fin("adn.in");
ofstream fout("adn.out");
void solve(int x, int ii){
    if(t[x][ii] == 0){
        for(int i = 1; i <= m[ii]; i++){
            fout<< s[ii][i];
        }
        return;
    }
    int y = t[x][ii];
    solve(x - (1 << ii), y);
    for(int i = a[y][ii] + 1; i <= m[ii]; i++){
        fout<< s[ii][i];
    }
}
int main(){
    fin>> n;
    for(i = 0; i < n; i++){
        fin>> s[i] + 1;
        m[i] = strlen(s[i] + 1);
    }
    for(ii = 0; ii < n; ii++){
        L = 0;
        for(i = 2; i <= m[ii]; i++){
            while(L != 0 && s[ii][L + 1] != s[ii][i]){
                L = p[L];
            }
            if(s[ii][L + 1] == s[ii][i]){
                L++;
            }
            p[i] = L;
        }
        for(jj = 0; jj < n; jj++){
            L = 0;
            for(i = 1; i <= m[jj]; i++){
                while(L != 0 && s[ii][L + 1] != s[jj][i]){
                    L = p[L];
                }
                if(s[ii][L + 1] == s[jj][i]){
                    L++;
                }
                if(L == m[ii] && ii != jj){
                    ok[ii] = 1;
                }
            }
            a[jj][ii] = L;
        }
    }
    for(ii = 0; ii < (1 << n); ii++){
        for(i = 0; i < n; i++){
            d[ii][i] = 1000000000;
        }
    }
    for(i = 0; i < n; i++){
        d[ (1 << i) ][i] = m[i];
    }
    for(ii = 2; ii < (1 << n); ii++){
        for(i = 0; i < n; i++){
            if(d[ii][i] != 1000000000 || ( (ii >> i) & 1) == 0){
                continue;
            }
            for(j = 0; j < n; j++){
                if(i != j){
                    if(d[ii][i] > d[ii - (1 << i)][j] + m[i] - a[j][i]){
                        d[ii][i] = d[ii - (1 << i)][j] + m[i] - a[j][i];
                        t[ii][i] = j;
                    }
                }
            }
        }
    }
    for(i = 0; i < n; i++){
        if(ok[i] == 0){
            x += (1 << i);
        }
    }
    ii = 0;
    for(i = 1; i < n; i++){
        if(d[x][i] < d[x][ii]){
            ii = i;
        }
    }
    solve(x, ii);
    return 0;
}