Cod sursa(job #1202002)

Utilizator SerejaSereja Sereja Data 26 iunie 2014 16:55:14
Problema ADN Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.26 kb
#include <fstream>
#include <cstring>
#include <string>
using namespace std;
const int INF = 0x3f3f3f3f;
int n, MaxConf,len[18], Length;
char a[18][30004];
int dp[1<<18][18], pre[1<<18][18], PI[18][30004], mat[18][18];
string Solution;
ofstream g("adn.out");
inline void Read(){
    ifstream f("adn.in");
    f >> n;
    char s[30004];
    for(int i = 0;i < n; ++i){
        f >> (s+1);
        strcpy(a[i]+1,s+1);
        len[i] = strlen(s+1);
        PI[i][1] = 0;
        int k = 0;
        for(int j = 2;j <= len[i]; ++j){
           while(k && s[k+1] != s[j]) 
               k = PI[i][k];
           if(s[k+1]==s[j])
              ++k;
            PI[i][j] = k;
        } 
    }
}

inline int F(char *s1,const int n,char *s2,const int m,int pi[]){
   int k = 0;
   for(int i = 1;i <= n; ++i){
       while(k && s2[k+1] != s1[i])
           k = pi[k];
        if(s2[k+1] == s1[i])
            ++k;
        if(k==m)
            return -1;
   }
   return k;
}
inline void Solve1(){ 
    memset(dp,INF,sizeof(dp));
    for(int i = 0;i < n;++i)
        dp[1<<i][i] = len[i];
    for(int conf = 1; conf < MaxConf; ++conf)
        for(int j = 0;j < n; ++j){
            pre[conf][j] = -1;
            if(dp[conf][j] == INF && (conf&(1<<j)) != 0){
                    int minn = INF; 
                    if(conf-(1<<j)==0)
                        continue;
                    int last = -1;
                    for(int k = 0;k < n; ++k)
                        if((conf&(1<<k))!=0){
                            int x = dp[conf-(1<<j)][k] + len[j]-mat[k][j]; 
                            if(x <= minn){
                                minn = x;
                                last = k;
                            }
                        }
                    dp[conf][j] = minn;
                    pre[conf][j] = last; 
                }
          }
}

inline string Reconst(const int conf,const int x){
    string ret;
    if(pre[conf][x]!=-1){
        ret = Reconst(conf-(1<<x),pre[conf][x]); 
        int i = mat[pre[conf][x]][x]+1;
        for(; i <= len[x]; ++i)
            ret = ret+ a[x][i];
    }
    else
        for(int i = 1;i <= len[x]; ++i)
            ret = ret + a[x][i];
    return ret;
}

inline void Solve(){
    for(int i = 0;i < n; ++i)
        for(int j = 0;j < n; ++j)
            if(i != j){
                int x = F(a[i],len[i],a[j],len[j],PI[j]);
                if(x==-1){
                   for(int k = j;k < n; ++k){
                        strcpy(a[k]+1,a[k+1]+1);
                        len[k] = len[k+1];
                        for(int p = 1;p <= len[k];++p)
                            PI[k][p] = PI[k+1][p];
                   }
                   --n;
                   i -= 2;
                   j = n+1;
                }
        }
    for(int i = 0;i < n; ++i)
        for(int j = 0;j < n;++j)
            if(i!=j)
                mat[i][j] = F(a[i],len[i],a[j],len[j],PI[j]); 
    
    MaxConf = 1<<n;
    Length = INF;
    Solve1();
    int L = INF;
    int i = -1;
    for(int j = 0;j < n; ++j)
        if(dp[MaxConf-1][j] < L){
                L = dp[MaxConf-1][j];
                i = j;
            }
        if(L < Length){
            Length = L;
            Solution = Reconst(MaxConf-1,i);
        }
    g<<Solution<<"\n";
}

int main(){
    Read();
    Solve();
    return 0;
}