Cod sursa(job #695869)

Utilizator darrenRares Buhai darren Data 28 februarie 2012 15:16:26
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.32 kb
#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[20], in[20][20], pos[20];
int Q[30010], minL[1 << 18][20], T[1 << 18][20];
bool nok[18];
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[pos[y]] + 1;
	else
	{
		int howmuch = minL[x][y] - minL[x ^ (1 << y)][T[x][y]];
		fout << A[pos[y]] + size[pos[y]] - howmuch + 1;
	}
}

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;
					nok[i] = true;
				}
				else
					in[i][j] = size[i] - qnow;
			}
	for (int i = 0; i < N; ++i)
		if (!nok[i])
			pos[pos[N]++] = i;
	
	N = pos[N];
	for (int i = 0; i < (1 << N); ++i)
		for (int j = 0; j < N; ++j)
			minL[i][j] = INF;
	
	for (int i = 0; i < N; ++i)
	{
		minL[1 << i][i] = size[pos[i]];
		T[1 << i][i] = 0;
	}
	for (int i = 1; i < (1 << N); ++i)
		if (i & (i - 1))
			for (int j = 0; j < N; ++j)
				if (i & (1 << j))
					for (int k = 0; k < N; ++k)
						if (k != j && (i & (1 << k)))
							if (minL[i ^ (1 << j)][k] + in[pos[j]][pos[k]] < minL[i][j])
							{
								minL[i][j] = minL[i ^ (1 << j)][k] + in[pos[j]][pos[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();
}