Cod sursa(job #695686)

Utilizator darrenRares Buhai darren Data 28 februarie 2012 13:55:31
Problema ADN Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.51 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];
int Q[30010], minL[1 << 18][20], T[2][1 << 18][20];
bool linkn[1 << 18][20];
int result = INF;

void track(int x, int y)
{
	if (x == 0) return;
	track(T[1][x][y], T[0][x][y]);
	
	if (!linkn[x][y])
	{
		if ((x ^ (1 << y)) == 0)
			fout << A[y] + 1;
		else
		{
			int howmuch = minL[x][y] - minL[T[1][x][y]][T[0][x][y]];
			fout << A[y] + size[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;
				else
					in[i][j] = size[i] - qnow;
			}
	
	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[i];
		T[0][1 << i][i] = 0;
		T[1][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[j][k] < minL[i][j])
							{
								linkn[i][j] = false;
								minL[i][j] = minL[i ^ (1 << j)][k] + in[j][k];
								T[0][i][j] = k;
								T[1][i][j] = i ^ (1 << j);
								if (in[j][k] == 0 && minL[i][j] < minL[i][k])
								{
									linkn[i][k] = true;
									minL[i][k] = minL[i][j];
									T[0][i][k] = T[0][i][j];
									T[1][i][k] = T[1][i][j];
								}
							}
	
	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();
}