Cod sursa(job #1588045)

Utilizator SilviuIIon Silviu SilviuI Data 2 februarie 2016 19:12:57
Problema ADN Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 4.17 kb
#include <stdio.h>
#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
#define lmax 30010

using namespace std;

int n,st,nr;
int dp[20][lmax*10],path[20][lmax*10];
int urm[lmax],dif[20][20],sol[20];
bool del[20],viz[20][lmax*10];
string s[20];
char ss[lmax];
vector < pair<int,int> > g[20];

int memo(int nod,int mask)
{
    if (viz[nod][mask]) return dp[nod][mask];
    viz[nod][mask]=true;
    for (unsigned int i=0;i<g[nod].size();i++) {
        int y=g[nod][i].first;
        if (((mask>>(y-1))&1)==1) {
            if (y==st && mask-(1<<(nod-1))!=1<<(y-1)) continue;
            int val=memo(y,mask-(1<<(nod-1)))+g[nod][i].second;
            if (val>dp[nod][mask]) {
                dp[nod][mask]=val; path[nod][mask]=y;
            }
        }
    }
    return dp[nod][mask];
}

int nrbit(int x) { return (x&(x-1)); }

void findpath(int nod,int mask)
{
    if (mask==(1<<(st-1))) return; else
    {
        int x=path[nod][mask];
        nr++; sol[nr]=nod;
        findpath(x,mask-(1<<(nod-1)));
    }
}

int main()
{
    freopen("adn.in","r",stdin);
    freopen("adn.out","w",stdout);

    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%s",ss); s[i]=ss; s[i].insert(0," ");
    }

    for (int i=1;i<=n;i++)
        if (!del[i]) {
            for (int j=1;j<=n;j++)
                if (i!=j && !del[j]) {
                    urm[1]=0; int k=0;
                    for (int l=2;l<(int)s[i].size();l++) {
                        while (k>0 && s[i][l]!=s[i][k+1]) k=urm[k];
                        if (s[i][l]==s[i][k+1]) k++;
                        urm[l]=k;
                    }

                    bool ok=false; k=0;
                    for (int l=1;l<(int)s[j].size();l++) {
                        while (k>0 && s[j][l]!=s[i][k+1]) k=urm[k];
                        if (s[j][l]==s[i][k+1]) k++;
                        if (k==s[i].size()-1) { ok=true; break; }
                    }

                    if (ok) { del[i]=true; break; }
                }
    }

    int m=0;
    for (int i=1;i<=n;i++)
        if (!del[i]) { m++; s[m]=s[i]; }

    n=m;

    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++)
        if (i!=j) {
            /*verific daca sufixul lui s[i] se regaseste ca prefix in s[j]; */
            urm[1]=0; int k=0;
            for (int l=2;l<(int)s[j].size();l++) {
                while (k>0 && s[j][l]!=s[j][k+1]) k=urm[k];
                if (s[j][l]==s[j][k+1]) k++;
                urm[l]=k;
            }

            k=0;
            for (int l=1;l<(int)s[i].size();l++) {
                while (k>0 && s[i][l]!=s[j][k+1]) k=urm[k];
                if (s[i][l]==s[j][k+1]) k++;
                if (k==s[j].size()-1) k=urm[k];
            }

            g[j].push_back(make_pair(i,k)); dif[j][i]=k;
        }
    }

    for (int i=1;i<=n;i++) s[i].erase(s[i].begin());

    int maxx=(1<<n)-1,best=-1,ind=0;

    for (int l=1;l<=n;l++) {
        st=l;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=maxx;j++)
                dp[i][j]=-1,viz[i][j]=false;

            dp[st][1<<(st-1)]=0; viz[st][1<<(st-1)]=true;
            for (int j=0;j<(int)g[st].size();j++) {
                int val=memo(g[st][j].first,maxx);
                if (val>dp[st][maxx]) {
                   dp[st][maxx]=val; path[st][maxx]=g[st][j].first;
                }
            }
        if (dp[st][maxx]>best) {
            ind=l; best=dp[st][maxx];
        }
    }



    if (n==1) dp[1][maxx]=0; st=ind;

    for (int i=1;i<=n;i++)
        for (int j=1;j<=maxx;j++)
            dp[i][j]=-1,viz[i][j]=false;

    dp[st][1<<(st-1)]=0; viz[st][1<<(st-1)]=true;
    for (int j=0;j<(int)g[st].size();j++) {
        int val=memo(g[st][j].first,maxx);
        if (val>dp[st][maxx]) {
            dp[st][maxx]=val; path[st][maxx]=g[st][j].first;
        }
    }

    findpath(path[ind][maxx],maxx);
    nr++; sol[nr]=ind;

    reverse(sol+1,sol+nr+1);

    for (int i=1;i<nr;i++) {
        int y=dif[sol[i+1]][sol[i]];
        for (int j=0;j<s[sol[i]].size()-y;j++) printf("%c",s[sol[i]][j]);
    }

    cout<<s[sol[nr]];

    return 0;
}