Cod sursa(job #1740583)

Utilizator mariusn01Marius Nicoli mariusn01 Data 11 august 2016 20:00:42
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.68 kb
#include <fstream>
#include <iostream>
#include <cstring>
#define DIM 30010

using namespace std;

char s[19][DIM];
int p[19][DIM];

int A[19][19];
int out[19];
int Len[19];
int D[(1<<19)+1][20], T[(1<<19)+1][20];
int n;

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

void prefix(int sir) {
    int q = 0;
    p[sir][1] = 0;
    for (int i=2; s[sir][i] != 0; i++) {
        while (q!=0 && s[sir][i] != s[sir][q+1])
            q = p[sir][q];
        if (s[sir][q+1] == s[sir][i])
            q++;
        p[sir][i] = q;
    }
}

void drum(int stare, int b) {
    if ((stare&(stare-1)) == 0) {
        fout<<s[b]+1;
    } else {
        drum(stare - (1<<b), T[stare][b]);
        // afisez ultimele A[T[stare][b]][b] caractere din s[b]
        for (int i=Len[b]-A[T[stare][b]][b]+1; i<=Len[b];i++)
            fout<<s[b][i];
    }
}

int main () {

    fin>>n;
    for (int i=0;i<n;i++) {
        fin>>s[i]+1;
        Len[i] = strlen(s[i]+1);
        prefix(i);
    }

    for (int i=0;i<n;i++)
        for (int j=0;j<n;j++) {
            if (i == j)
                continue;
            // caut cel mai lung prefix al lui j care este sufix al lui i
            // practic caut daca sirul j se gaseste in sirul i
            int q = 0;
            for (int ii=1;s[i][ii]!=0;ii++) {
                while (q!=0 && s[j][q+1] != s[i][ii])
                    q = p[j][q];
                if (s[j][q+1] == s[i][ii])
                    q++;
                if (q == Len[j]) {
                    q = p[j][ Len[j] ];
                    out[j] = 1;
                }
                if (ii == Len[i] && out[j] == 0) {
                    A[i][j] = Len[j]-q;
                }
            }
        }
    for (int i=0;i<n;i++) {
        if (out[i] == 1) {
            // elimin cuvantul i
            for (int lin=i;lin<n-1;lin++) {
                for (int col = 0; col < n; col++)
                    A[lin][col] = A[lin+1][col];
                out[lin] = out[lin+1];
                Len[lin] = Len[lin+1];
                strcpy(s[lin]+1, s[lin+1]+1);
            }
            for (int col=i;col<n-1;col++)
                for (int lin=0;lin<n;lin++)
                    A[lin][col] = A[lin][col+1];
            n--;
            i--;
        }
    }

/*
    cout <<n<<"\n";
    for (int i=0;i<n;i++) {
        cout<<s[i]+1<<"\n";
    }

    for (int i=0;i<n;i++) {
        for (int j=0;j<n;j++)
            cout<<A[i][j] <<" ";
        cout<<"\n";
    }
*/
    //ciclu (de fapt lant) hamiltonian de cost minim
    int INF = 1 + (1<<8) + (1<<16) + (1<<24);

    memset(D, 1, sizeof(D));
    for (int stare = 1; stare<(1<<n); stare++) {
        if ((stare &(stare-1)) == 0) {
            for (int b=0;b<n;b++)
                if ((stare >> b) & 1) {
                    D[stare][b] = Len[b];
                    break;
                }
        }
        for (int b=0;b<n;b++) {
            if ((stare >> b) & 1) {
                // sunt in [stare][b] si adaug un nou nod
                for (int nextb = 0; nextb<n; nextb++) {
                    if (((stare >> nextb) & 1) == 0) {
                        if (D[stare + (1<<nextb)][nextb] > D[stare][b] + A[b][nextb]) {
                            D[stare + (1<<nextb)][nextb] = D[stare][b] + A[b][nextb];
                            T[stare + (1<<nextb)][nextb] = b;
                        }
                    }
                }
            }
        }
    }
    int sol = INF, u;
    for (int b=0;b<n;b++) {
        if (sol > D[(1<<n)-1][b]) {
            sol = D[(1<<n)-1][b];
            u = b;
        }
    }

    drum((1<<n)-1, u);

//    fout<<sol;
    return 0;
}