Cod sursa(job #3036594)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 24 martie 2023 17:15:37
Problema ADN Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.93 kb
#include <fstream>
#include <string>
#include <vector>

#pragma GCC optimize ("Ofast")

using namespace std;

#define inf 0x3f3f3f3f

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

string s[20], a;
int p[60001], c[20][20], r[20];
int n, x, rasp[20];
vector <int> v[20];
pair <int, int> dp[262300][20];


bool kmp (int x, int y)
{
    int k;
	a = s[y] + '#' + s[x];
	for(int i = 1; i < (int) a.size(); i++)
	{
		k = p[i - 1];
		while (k > 0 && a[i] != a[k])
			k = p[k - 1];
		if (a[i] == a[k])
			k++;
		p[i] = k;
		if (p[i] == (int) s[y].size())
			return 1;
	}
	c[x][y] = (int) s[y].size() - (int) p[a.size() - 1];
	return 0;
}

int calc()
{
	int m = 0, i, j;
	bool ok[18] = {};
	for (i = 0; i < n; i++)
		for (j = 0; j < n; j++)
			if (i != j)
				ok[j] = ok[j] | kmp(i, j);

	for (i = 0; i<n; i++)
		if (ok[i] == 0)
		{
			r[m] = i;
			m++;
		}
	return m;
}

int main()
{
	fin >> n;
	for(int i = 0; i < n; i++)
		fin >> s[i];
	n = calc();
	for(int i = 0; i < (1 << n); i++)
		v[__builtin_popcount(i)].push_back(i);
	for(int i = 0; i < n; i++)
		dp[1 << i][i] = { (int) s[r[i]].size(), -1};
	for(int i = 2; i <= n; i++)
		for(int j = 0; j < (int) v[i].size(); j++)
		{
			x = v[i][j];
			for(int k = 0; k < n; k++)
				if (x & (1 << k))
				{
					dp[x][k] = {inf, 0};
					for(int y = 0; y < n; y++)
						if ((x ^ (1 << k)) & (1 << y))
							dp[x][k] = min(dp[x][k], {dp[x ^ (1<<k)][y].first + c[r[y]][r[k]], y});
				}
		}
	x = 0;
	for(int i = 1; i < n; i++)
		if (dp[(1 << n) - 1][i].first < dp[(1 << n) - 1][x].first)
			x = i;
	for(int i = x, j = (1<<n)-1; i != -1; j = j ^ (1<<i), i = dp[j ^ (1<<i)][i].second)
		rasp[++rasp[0]] = i;
	fout << s[r[rasp[rasp[0]]]];
	for(int i = rasp[0] - 1; i >= 1; i--)
	{
		x = c[r[rasp[i + 1]]][r[rasp[i]]];
		for(int j = (int) s[r[rasp[i]]].size() - x; j < (int) s[r[rasp[i]]].size(); j++)
			fout << s[r[rasp[i]]][j];
	}
	return 0;
}