Cod sursa(job #2632500)

Utilizator NicolaalexandraNicola Alexandra Mihaela Nicolaalexandra Data 3 iulie 2020 15:19:49
Problema ADN Scor 60
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.83 kb
#include <bits/stdc++.h>
#define DIMN 19
#define DIM 30010
#define INF 2000000000
using namespace std;

char s[DIMN][DIM];
int dp[(1<<DIMN)][DIMN],lg[DIMN],p[DIM],fth[(1<<DIMN)][DIMN],cst[DIMN][DIMN],f[DIMN];
int n,i,j,t;
vector <pair<int,int> > L[DIMN];
vector <int> v;

int main (){

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

    fin>>n;
    for (i=1;i<=n;i++){
        fin>>s[i]+1;
        lg[i] = strlen (s[i]+1);
    }

    for (i=1;i<=n;i++){

        /// verific daca e subsecventa in celelalte siruri
        memset (p,0,sizeof p);
        int l = 0;
        for (j=2;j<=lg[i];j++){
            while (l && s[i][j] != s[i][l+1])
                l = p[l];
            if (s[i][j] == s[i][l+1])
                l++;
            p[j] = l;
        }


        for (j=1;j<=n;j++){
            if (i == j)
                continue;

            int l = 0, ok = 0;
            for (t=1;t<=lg[j];t++){
                while (l && s[j][t] != s[i][l+1])
                    l = p[l];
                if (s[j][t] == s[i][l+1])
                    l++;
                if (l == lg[i]){
                    ok = 1;
                    break;
                }
            }

            if (ok){
                L[i-1].push_back(make_pair(j-1,0));
                f[i] = 1;
                cst[j-1][i-1] = 0;
            } else {
                L[i-1].push_back(make_pair(j-1,lg[i] - l));
                cst[j-1][i-1] = lg[i] - l;
            }}}

    for (i=0;i<(1<<n);i++)
        for (j=0;j<n;j++)
            dp[i][j] = INF;

    for (i=0;i<n;i++)
        if (!f[i+1])
            dp[(1<<i)][i] = lg[i+1];

    for (int stare=1;stare<(1<<n);stare++){

        for (i=0;i<n;i++){
            if (!(stare & (1<<i)))
                continue;

            for (auto it : L[i]){
                int vecin = it.first, cost = it.second;
                if (!(stare & (1<<vecin)))
                    continue;
                if (dp[stare-(1<<i)][vecin] + cost < dp[stare][i]){
                    dp[stare][i] = dp[stare-(1<<i)][vecin] + cost;
                    fth[stare][i] = vecin;
                }}}}

    int sol = INF, last = 0;
    for (i=0;i<n;i++){
        if (dp[(1<<n)-1][i] < sol){
            sol = dp[(1<<n)-1][i];
            last = i;
        }
    }

    int x = (1<<n)-1, y = last;
    v.push_back(y);
    while (x){
        int aux = (1<<y);
        y = fth[x][y];
        x -= aux;
        v.push_back(y);
    }

    v.pop_back();
    reverse (v.begin(),v.end());
    //for (auto it : v)
       // cout<<it+1<<" ";

    fout<<s[v[0]+1]+1;
    for (i=1;i<v.size();i++){
        int idx = v[i] + 1, val = cst[v[i-1]][v[i]];
        for (j=lg[idx]-val+1;j<=lg[idx];j++)
            fout<<s[idx][j];
    }


    //fout<<"\n"<<sol;


    return 0;
}