Cod sursa(job #2741307)

Utilizator PatrickCplusplusPatrick Kristian Ondreovici PatrickCplusplus Data 15 aprilie 2021 20:42:18
Problema ADN Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, s[(1 << 20)];
string v[20];
string dp[(1 << 20)];

string getNewString(string &a, string &b){
    for (int i = 0; i < a.size(); ++i){
        bool ok = true;
        int j = 0, k = i;
        while (j < b.size() && k < b.size()){
            if (b[j] != a[k]){
                ok = false;
                break;
            }
            ++j;
            ++k;
        }
        if (ok){
            string aux = a;
            int idk = n - i;
            while (idk < b.size()){
                aux += b[idk++];
            }
            return aux;
        }
    }
    string aux = a;
    for (int j = 0; j < b.size(); ++j){
        aux += b[j];
    }
    return aux;
}

int main(){
    fin >> n;
    for (int i = 1; i <= n; ++i){
        fin >> v[i];
        dp[(1 << (i - 1))] = v[i];
    }
    for (int i = 0; i < (1 << n); ++i){
        s[i] = (1 << 30);
    }
    for (int i = 1; i < (1 << n); ++i){
        if (dp[i] != ""){
            for (int j = 0; j < n; ++j){
                if (((i >> j) & 1) == 0){
                    string aux = getNewString(dp[i], v[j + 1]);
                    if (aux.size() < s[(i | (1 << j))]){
                        s[(i | (1 << j))] = aux.size();
                        dp[(i | (1 << j))] = aux;
                    }
                }
            }
        }
    }
    fout << dp[(1 << n) - 1];
    fin.close();
    fout.close();
    return 0;
}