Pagini recente » Cod sursa (job #2095317) | Cod sursa (job #305006) | Cod sursa (job #382071) | Cod sursa (job #2119730) | Cod sursa (job #695557)
Cod sursa(job #695557)
#include <cstring>
#include <fstream>
using namespace std;
const int INF = 0x3f3f3f3f;
ifstream fin("adn.in");
ofstream fout("adn.out");
int N;
char A[18][30010];
int size[18], in[20][20];
int Q[30010], minL[1 << 18][20], T[1 << 18][20];
int result = INF;
void track(int x, int y)
{
if (x == 0) return;
track(x ^ (1 << y), T[x][y]);
if ((x ^ (1 << y)) == 0)
fout << A[y] + 1;
else
{
int howmuch = minL[x][y] - minL[x ^ (1 << y)][T[x][y]];
fout << A[y] + 1 + size[y] - howmuch;
}
}
int main()
{
fin >> N;
for (int i = 0; i < N; ++i)
{
fin >> A[i];
size[i] = strlen(A[i]);
for (int j = size[i]; j >= 1; --j)
A[i][j] = A[i][j - 1];
}
for (int i = 0; i < N; ++i)
for (int j = 0; j < N; ++j)
if (i != j)
{
memset(Q, 0, sizeof(Q));
int qnow = 0;
for (int k = 2; k <= size[i]; ++k)
{
while (qnow && A[i][qnow + 1] != A[i][k])
qnow = Q[qnow];
if (A[i][qnow + 1] == A[i][k]) ++qnow;
Q[k] = qnow;
}
bool isok = false;
qnow = 0;
for (int k = 1; k <= size[j]; ++k)
{
while (qnow && A[i][qnow + 1] != A[j][k])
qnow = Q[qnow];
if (A[i][qnow + 1] == A[j][k])
++qnow;
if (qnow == size[i])
{
isok = true;
qnow = Q[qnow];
}
}
if (isok)
in[i][j] = 0;
else
in[i][j] = size[i] - qnow;
}
for (int i = 0; i < N; ++i)
{
minL[1 << i][i] = size[i];
T[1 << i][i] = i;
}
for (int i = 1; i < (1 << N); ++i)
if (i & (i - 1))
for (int j = 0; j < N; ++j)
{
minL[i][j] = INF;
if (i & (1 << j))
for (int k = 0; k < N; ++k)
if (k != j && (i & (1 << k)))
if (minL[i ^ (1 << j)][k] + in[j][k] < minL[i][j])
{
minL[i][j] = minL[i ^ (1 << j)][k] + in[j][k];
T[i][j] = k;
}
}
result = N, minL[(1 << N) - 1][result] = INF;
for (int i = 0; i < N; ++i)
if (minL[(1 << N) - 1][i] < minL[(1 << N) - 1][result])
result = i;
track((1 << N) - 1, result);
fout << '\n';
fin.close();
fout.close();
}