Cod sursa(job #998044)

Utilizator poptibiPop Tiberiu poptibi Data 15 septembrie 2013 16:24:00
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.43 kb
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;

const int NMAX = 20, LMAX = 30005, INF = 0x3f3f3f3f;

int N, PI[NMAX][LMAX], Cost[NMAX][NMAX], DP[1 << NMAX][NMAX], Prev[1 << NMAX][NMAX], Elim[NMAX], Len[NMAX], FinalConf;
char S[NMAX][LMAX];

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

void Prefix(int Idx)
{
    int i, Q = 0;
    PI[Idx][1] = 0;
    for(i = 2; i <= Len[Idx]; ++ i)
    {
        while(Q && S[Idx][Q + 1] != S[Idx][i]) Q = PI[Idx][Q];
        if(S[Idx][Q + 1] == S[Idx][i]) Q ++;
        PI[Idx][i] = Q;
    }
}

int GetCost(int IdxA, int IdxB)
{
    int i, Q = 0;
    for(int i = 1; i <= Len[IdxA]; ++ i)
    {
        while(Q && S[IdxB][Q + 1] != S[IdxA][i]) Q = PI[IdxB][Q];
        if(S[IdxB][Q + 1] == S[IdxA][i]) Q ++;
        if(Q == Len[IdxB]) return Q;
    }
    return Q;
}

void GoBack(int Conf, int Last)
{
    if(Conf == (1 << Last))
    {
        fout << S[Last] + 1;
        return ;
    }
    GoBack(Conf - (1 << Last), Prev[Conf][Last]);
    fout << S[Last] + 1 - Cost[Prev[Conf][Last]][Last];
}

int main()
{
    fin >> N;
    for(int i = 0; i < N; ++ i)
    {
        fin >> (S[i] + 1);
        Len[i] = strlen(S[i] + 1);
        Prefix(i);
    }

    for(int i = 0; i < N; ++ i)
        for(int j = i + 1; j < N; ++ j)
        {
            int ij = GetCost(i, j), ji = GetCost(j, i);
            Cost[i][j] = -ij;
            Cost[j][i] = -ji;

            if(ij == Len[j]) Elim[j] = 1;
            else if(ji == Len[i]) Elim[i] = 1;
        }

    memset(DP, INF, sizeof(DP));
    for(int i = 0; i < N; ++ i)
        if(!Elim[i])
        {
            FinalConf += (1 << i);
            DP[1 << i][i] = 0;
        }

    for(int Conf = 1; Conf < (1 << N); ++ Conf)
        for(int i = 0; i < N; ++ i)
            if(!Elim[i] && (Conf & (1 << i)) && DP[Conf][i] != INF)
                for(int j = 0; j < N; ++ j)
                    if(!Elim[j] && !(Conf & (1 << j)) && DP[Conf ^ (1 << j)][j] > DP[Conf][i] + Cost[i][j])
                    {
                        DP[Conf ^ (1 << j)][j] = DP[Conf][i] + Cost[i][j];
                        Prev[Conf ^ (1 << j)][j] = i;
                    }

    int LastS = -1;
    for(int i = 0; i < N; ++ i)
        if(DP[FinalConf][LastS] > DP[FinalConf][i])
            LastS = i;

    GoBack(FinalConf, LastS);

    return 0;
}