Cod sursa(job #2962570)

Utilizator NefelibataAnton Marius Alexandru Nefelibata Data 8 ianuarie 2023 18:54:57
Problema ADN Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.23 kb
#include<iostream>
#include<fstream>
#include <bits/stdc++.h>
#include <climits>

using namespace std;

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

const int inf = INT_MAX;
const int NMAX = 22;
vector <string> v;
string s;
int n,pi[NMAX][3010],m,mat[NMAX][NMAX];
bool is[NMAX];
int dp[NMAX][1 << NMAX], best[NMAX][1 << NMAX], ord[NMAX];

void prefix(int i){
    int q = 0,j;
    pi[i][1] = 0;
    for(j = 2 ; j <= m ; j++){
        while(q && v[i][q + 1] != v[i][j])
            q = pi[i][q];
        if(v[i][q + 1] == v[i][j])
            q++;
        pi[i][j] = q;
    }
}

int superposition(int i, int j){
    int m = v[i].size() - 1;
    int n = v[j].size() - 1;
    int q = 0;
    for(int ii = 1 ; ii <= m ; ii++){
        while(q > 0 && v[j][q + 1] != v[i][ii])
            q = pi[j][q];
        if(v[j][q + 1] == v[i][ii])
            q++;
        if(q == n)
            return inf;
    }
    return n - q;
}

bool exists(int i){
    int q,j,jj;
    for(jj = 0 ; jj < n ; jj++)
        if(jj != i){
            q = 0;
            m = v[j].size() - 1;
            for(j = 1 ; j <= m ; j++){
                while(q && v[i][q + 1] != v[jj][j])
                    q = pi[i][q];
                if(v[i][q + 1] == v[jj][j])
                    q++;
                if(q == v[i].size() - 1)
                    return 1;
            }
        }
    return 0;
}

int main(){
    int i,j,ii,q;
    f >> n;
    for(i = 1 ; i <= n ; i++){
        f >> s;
        v.push_back(' ' + s);
        is[i - 1] = 1;
    }
    for(i = 0 ; i < n ; i++){
        m = v[i].size() - 1;
        prefix(i);
    }
    int all = (1 << n) - 1;
    int nr = n;
    for(i = 0 ; i < n ; i++)
        for(j = 0 ; j < n ; j++)
            if(i != j && (all & (1 << j))){
                mat[i][j] = superposition(i,j);
                if(mat[i][j] == inf){
                    all ^= (1 << j);
                    nr--;
                }
            }
    for(i = 0 ; i < n ; i++)
        for(j = 0 ; j < (1 << n) ; j++)
            dp[i][j] = inf;
    for(i = 0 ; i < n ; i++)
        dp[i][1 << i] = v[i].size() - 1;

    for(i = 1 ; i <= all ; i++)
        for(j = 0 ; j < n ; j++)
            if( (i & (1 << j)) && (all & (1 << j)))
                for(ii = 0 ; ii < n ; ii++)
                    if( !(i & (1 << ii)) && (all & (1 << ii)) && dp[ii][i ^ (1 << ii)] > dp[j][i] + mat[j][ii]){
                        dp[ii][i ^ (1 << ii)] = dp[j][i] + mat[j][ii];
                        best[ii][i ^ (1 << ii)] = j;
                    }

    int minim = inf;
    int pos = 0;
    for(i = 0 ; i < n ; i++)
        if((all & (1 << i)) && dp[i][all] < minim){
            minim = dp[i][all];
            pos = i;
        }
    int poz = nr, cnr = all;
    ord[poz--] = pos;
    for(i = 2 ; i <= nr ; i++){
        int aux = pos;
        pos = best[pos][cnr];
        cnr ^= (1 << aux);
        ord[poz--] = pos;
    }
    for(i = 0 ; i < n ; i++)
        v[i].erase(v[i].begin());
    o << v[ord[1]];
    for(i = 2 ; i <= nr ; i++){
        for(j = v[ord[i]].size() - mat[ord[i - 1]][ord[i]] ; j < v[ord[i]].size() ; j++)
            o << v[ord[i]][j];
    }
    f.close();
    o.close();
    return 0;
}