Pagini recente » Cod sursa (job #1053017) | Cod sursa (job #2346309) | Cod sursa (job #277242) | Cod sursa (job #1450955) | Cod sursa (job #2587478)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("adn.in");
ofstream fout ("adn.out");
const int NMAX = 20, LMAX = 30010;
int n, lg[NMAX], lps[NMAX][LMAX];
char sir[NMAX][LMAX];
int dist[NMAX][NMAX];
long long dp[1 << NMAX][NMAX], lgMin = LLONG_MAX;
int indAns[NMAX], nod;
void FindLPS(int ind)
{
int j = 0;
int i = 1;
lps[ind][0] = 0;
while (i < lg[ind])
{
if (sir[ind][i] == sir[ind][j])
{
lps[ind][i] = j + 1;
i++;
j++;
}
else
{
if (j != 0)
j = lps[ind][j - 1];
else
{
lps[ind][i] = 0;
i++;
}
}
}
}
void CalcDist(int ind1, int ind2)
{
int i = 0;
int j = 0;
while (i < lg[ind1])
{
if (sir[ind1][i] == sir[ind2][j])
{
i++;
j++;
if (j == lg[ind2])
{
dist[ind1][ind2] = 0;
return;
}
}
else
{
if (j != 0)
j = lps[ind2][j - 1];
else
i++;
}
}
dist[ind1][ind2] = lg[ind2] - j;
}
void SolveDP()
{
for (int mask = 1; mask < (1 << n); mask++)
for (int i = 1; i <= n; i++)
dp[mask][i] = LLONG_MAX;
for (int i = 1; i <= n; i++)
dp[1 << (i - 1)][i] = lg[i];
for (int mask = 1; mask < (1 << n); mask++)
{
for (int i = 1; i <= n; i++)
{
if (mask & (1 << (i - 1)))
{
for (int j = 1; j <= n; j++)
if (i != j && (mask & (1 << (j - 1))))
dp[mask][i] = min(dp[mask][i], dp[mask ^ (1 << (i - 1))][j] + dist[j][i]);
}
}
}
for (int i = 1; i <= n; i++)
{
if (lgMin > dp[(1 << n) - 1][i])
{
lgMin = dp[(1 << n) - 1][i];
nod = i;
}
}
}
void FindAns(int mask, int ind, long long val, int cnt)
{
if (mask > 0)
{
for (int i = 1; i <= n; i++)
{
if ((mask & (1 << (i - 1))) && dp[mask][i] + dist[i][ind] == val)
{
indAns[cnt] = i;
FindAns(mask ^ (1 << (i - 1)), i, val - dist[i][ind], cnt - 1);
break;
}
}
}
}
int main()
{
fin >> n;
for (int i = 1; i <= n; i++)
{
fin >> sir[i];
lg[i] = strlen(sir[i]);
FindLPS(i);
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
if (i != j)
CalcDist(i, j);
}
SolveDP();
FindAns(((1 << n) - 1) ^ (1 << (nod - 1)), nod, dp[(1 << n) - 1][nod], n - 1);
indAns[n] = nod;
fout << sir[indAns[1]];
for (int i = 2; i <= n; i++)
fout << (sir[indAns[i]] + lg[indAns[i]] - dist[indAns[i - 1]][indAns[i]]);
return 0;
}