Cod sursa(job #2962624)

Utilizator dimi999Dimitriu Andrei dimi999 Data 8 ianuarie 2023 21:16:47
Problema ADN Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.73 kb
#include<fstream>
#include <vector>

using namespace std;

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

vector <string> v;
int N, prefixes[20][30010], rest_add[20][20];
int dp[20][1 << 20], sol[20][1 << 20], order[20];

void kmp(int i){
    int common = 0;
    
    prefixes[i][1] = 0;
    for(int j = 2; j <= v[i].size(); j++){
        while(common != 0 && v[i][common + 1] != v[i][j])
            common = prefixes[i][common];
        if(v[i][common + 1] == v[i][j])
            common++;
        prefixes[i][j] = common;
    }
}

int compute(int i, int j){
    int aux = 0;
    for(int it = 1; it < v[i].size() ; it++){
        while(aux > 0 && v[j][aux + 1] != v[i][it])
            aux = prefixes[j][aux];
        if(v[j][aux + 1] == v[i][it])
            aux++;
        if(aux + 1 == v[j].size())
            return 1e9;
    }
    return v[j].size() - aux - 1;
}

int main(){
    fin >> N;
    
    for(int i = 1; i <= N; i++){
        string s; fin >> s;
        s = ' ' + s;
        v.push_back(s);
    }
    
    for(int i = 0; i < N; i++)
        kmp(i);

    for(int i = 0; i < N; i++) {
        for(int j = 0; j < (1 << N); j++)
            dp[i][j] = 1e9;
        dp[i][1 << i] = v[i].size() - 1;
    }
    
    int mask = (1 << N) - 1, nr = N;
    
    for(int i = 0; i < N; i++)
        for(int j = 0; j < N; j++)
            if(i != j && (mask & (1 << j))){
                rest_add[i][j] = compute(i, j);
                if(rest_add[i][j] == 1e9){
                    mask ^= (1 << j);
                    nr--;
                }
            }

    for(int i = 1; i <= mask; i++)
        for(int j = 0; j < N; j++)
            if((i & (1 << j)) && (mask & (1 << j)))
                for(int it = 0; it < N; it++)
                    if(!(i & (1 << it)) && (mask & (1 << it)) && dp[it][i ^ (1 << it)] > dp[j][i] + rest_add[j][it]){
                        dp[it][i ^ (1 << it)] = dp[j][i] + rest_add[j][it];
                        sol[it][i ^ (1 << it)] = j;
                    }

    int mini = 1e9, pos = 0;
    int poz = nr, crt = mask;
    
    for(int i = 0; i < N; i++)
        if((mask & (1 << i)) && dp[i][mask] < mini){
            mini = dp[i][mask];
            pos = i;
        }
    
    order[poz--] = pos;
    for(int i = 2; i <= nr; i++){
        int aux = pos;
        pos = sol[pos][crt];
        crt ^= (1 << aux);
        order[poz--] = pos;
    }
    
    for(int i = 0; i < N; i++)
        v[i].erase(v[i].begin());
    
    fout << v[order[1]];
    for(int i = 2 ; i <= nr; i++){
        for(int j = v[order[i]].size() - rest_add[order[i - 1]][order[i]]; j < v[order[i]].size(); j++)
            fout << v[order[i]][j];
    }
    return 0;
}