Pagini recente » Cod sursa (job #365513) | Cod sursa (job #1836091) | Cod sursa (job #573314) | Cod sursa (job #1789079) | Cod sursa (job #998044)
Cod sursa(job #998044)
#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;
}