Cod sursa(job #2703380)

Utilizator stefantagaTaga Stefan stefantaga Data 8 februarie 2021 14:48:27
Problema ADN Scor 40
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.71 kb
#include <bits/stdc++.h>

using namespace std;
ifstream f("adn.in");
ofstream g("adn.out");
struct wow
{
    int poz;
    int fr[20];
    vector <int> v;
    int cost;
}b,acum;
queue <wow> q;
vector <int> sol,v1;
int n,i,j,urm[30005],k,cost[20][20],fr[20],ok,maxim,ok1[20];
string s[20],s2;
int main()
{
    f>>n;
    for (i=1;i<=n;i++)
    {
        f>>s[i];
    }
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            if (i!=j)
            {
                s2=s[j]+'#'+s[i];
                urm[0]=0;
                k=0;
                for (int t=1;t<s2.size();t++)
                {
                    while (k>0&&s2[t]!=s2[k])
                    {
                        k=urm[k-1];
                    }
                    if (s2[t]==s2[k])
                    {
                        k++;
                    }
                    urm[t]=k;
                    if (urm[t]==s[j].size())
                    {
                        ok1[j]=1;
                    }
                }
                cost[i][j]=urm[s2.size()-1];
            }
        }
    }
    int minim=1e9;
    for (i=1;i<=n;i++)
    {
        for (j=1;j<=n;j++)
        {
            b.fr[j]=ok1[j];
        }
        b.v.clear();
        b.v.push_back(i);
        b.cost=s[i].size();
        b.poz=i;
        b.fr[i]=1;
        q.push(b);
        while (!q.empty())
        {
            acum=q.front();
            q.pop();
            ok=0;
            for (j=1;j<=n;j++)
            {
                if (acum.fr[j]==0)
                {
                    ok=1;
                    break;
                }
            }
            if (ok==0)
            {
                if (acum.cost<minim)
                {
                    minim=acum.cost;
                    sol.clear();
                    for (j=0;j<acum.v.size();j++)
                    {
                        sol.push_back(acum.v[j]);
                    }
                }
            }
            else
            {
                for (j=1;j<=n;j++)
                {
                    b=acum;
                    if (acum.fr[j]==0)
                    {
                        b.v.push_back(j);
                        b.fr[j]=1;
                        b.cost=b.cost+s[j].size()-cost[acum.v[acum.v.size()-1]][j];
                        b.poz=j;
                        q.push(b);
                    }
                }
            }
        }
    }
    g<<s[sol[0]];
    for (i=1;i<sol.size();i++)
    {
        int val1=sol[i-1],val2=sol[i];
        for (j=cost[val1][val2];j<s[val2].size();j++)
        {
            g<<s[val2][j];
        }
    }
    return 0;
}