Cod sursa(job #1532893)

Utilizator fanache99Constantin-Buliga Stefan fanache99 Data 21 noiembrie 2015 19:08:38
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.88 kb
#include<cstdio>
#include<cstring>
#include<vector>
#define inf 2000000000
using namespace std;
char s[20][30010];
int out[20],cost[20][20],prefix[20][30010],norm[20],rev[20],dp[300000][20],dad[300000][20],v[20],len[20];
vector<pair<int,int> > g[20];
void build_prefix(int index){
    int n=strlen(s[index]+1),i=0,j;
    prefix[index][1]=0;
    for(j=2;j<=n;j++){
        while(i>0&&s[index][i+1]!=s[index][j])
            i=prefix[index][i];
        if(s[index][i+1]==s[index][j])
            i++;
        prefix[index][j]=i;
    }
}
void kmp(int first,int second){
    int n=strlen(s[second]+1),m=strlen(s[first]+1),i=0,j,ok=1;
    for(j=1;j<=n&&ok==1;j++){
        while(i>0&&s[first][i+1]!=s[second][j])
            i=prefix[first][i];
        if(s[first][i+1]==s[second][j])
            i++;
        if(i==m){
            ok=0;
            cost[second][first]=0;
            out[first]=1;
        }
    }
    if(ok==1)
        cost[second][first]=m-i;
}
int main(){
    freopen("adn.in","r",stdin);
    freopen("adn.out","w",stdout);
    int n,i,j,k,nr=-1,dim,curr,answer=inf,config,temp;
    scanf("%d\n",&n);
    for(i=0;i<n;i++){
        scanf("%s",s[i]+1);
        len[i]=strlen(s[i]+1);
        build_prefix(i);
    }
    for(i=0;i<n;i++)
        for(j=0;j<n;j++){
            if(i==j)
                continue;
            kmp(i,j);
        }
    for(i=0;i<n;i++)
        if(out[i]==0){
            nr++;
            norm[i]=nr;
            rev[nr]=i;
        }
    for(i=0;i<n;i++)
        for(j=0;j<n;j++){
            if(i==j||out[i]==1||out[j]==1)
                continue;
            g[norm[j]].push_back(make_pair(norm[i],cost[i][j]));
        }
    nr++;
    for(i=0;i<(1<<nr);i++)
        for(j=0;j<nr;j++){
            dp[i][j]=inf;
            dad[i][j]=-1;
        }
    for(i=0;i<nr;i++){
        dp[1<<i][i]=strlen(s[rev[i]]+1);
        dad[1<<i][i]=-1;
    }
    for(i=0;i<(1<<nr);i++)
        for(j=0;j<nr;j++){
            if((i&(1<<j))==0||dp[i][j]!=inf)
                continue;
            dim=g[j].size();
            for(k=0;k<dim;k++){
                if((i&(1<<g[j][k].first))==0)
                    continue;
                if(dp[i][j]>dp[i-(1<<j)][g[j][k].first]+g[j][k].second){
                    dp[i][j]=dp[i-(1<<j)][g[j][k].first]+g[j][k].second;
                    dad[i][j]=g[j][k].first;
                }
            }
        }
    for(i=0;i<nr;i++)
        if(dp[(1<<nr)-1][i]<answer){
            answer=dp[(1<<nr)-1][i];
            curr=i;
        }
    k=0;
    config=(1<<nr)-1;
    i=curr;
    while(i!=-1){
        k++;
        v[k]=rev[i];
        temp=i;
        i=dad[config][i];
        config=config-(1<<temp);
    }

    printf("%s",s[v[nr]]+1);
    for(i=nr-1;i>=1;i--)
        for(j=cost[v[i+1]][v[i]];j>0;j--)
            printf("%c",s[v[i]][len[v[i]]-j+1]);
    return 0;
}