Pagini recente » Borderou de evaluare (job #2879681) | Cod sursa (job #2609379) | Borderou de evaluare (job #1500739) | Cod sursa (job #2169194) | Cod sursa (job #2459505)
#include <bits/stdc++.h>
#define nmax 19
#define lmax 30019
#define inf (1 << 30)
using namespace std;
ifstream f("adn.in");
ofstream g("adn.out");
string s[nmax];
int leng[nmax];
const int B = 197;
unsigned long long h[nmax][lmax], bpow[lmax];
int remain[nmax][nmax];
vector <int> sir;
bool pa[nmax];
int rez[1 << nmax][nmax];
int dp[1 << nmax][nmax];
bool duplicates(int a, int b)
{
unsigned long long hash = h[a][leng[a] - 1];
for (int i = 1; i + leng[a] - 1 < leng[b]; ++ i)
if (hash ==( h[b][i + leng[a] - 1] - h[b][i - 1] * bpow[leng[a]]))
{
pa[a] = 1;
return true;
}
return false;
}
void show_solution(int mask, int seed)
{
int prev = rez[mask][seed];
if (prev == -1)
{
g << s[sir[seed]];
return;
}
show_solution(mask ^ (1 << seed), prev);
for (int i = leng[sir[seed]] - remain[sir[prev]][sir[seed]]; i < leng[sir[seed]]; ++ i)
g << s[sir[seed]][i];
}
void make_hash(string s, int id)
{
h[id][0] = (int)s[0];
int len = s.length();
for (int i = 1; i < len; ++ i)
h[id][i] = h[id][i - 1] * B + s[i];
leng[id] = len;
}
int main()
{
int n;
f >> n;
for (int i = 0; i < n; ++ i)
{
f >> s[i];
make_hash(s[i], i);
}
bpow[0] = 1;
for (int i = 1; i < lmax; ++ i)
bpow[i] = bpow [i - 1] * B;
for (int i = 0; i < n; ++ i)
for (int j = 0; j < n; ++ j)
{
if (i == j || pa[i] || pa[j])
continue;
int a = i, b = j;
if (leng[i] > leng[j])
swap(a, b);
if (duplicates(a, b))
continue;
for (int k = leng[a]; k >= 0; -- k)
if (h[i][leng[i] - 1] - h[i][leng[i] - 1 - k] * bpow[k] == h[j][k - 1])
{
if (k == leng[a])
{
pa[a] = 1;
}
remain[i][j] = leng[j] - k;
break;
}
}
for (int i = 0; i < n; ++ i)
if (!pa[i])
sir.push_back(i);
n = sir.size();
for (int i = 0; i < n; ++ i)
{
dp[1 << i][i] = leng[sir[i]];
rez[1 << i][i] = -1;
}
for (int mask = 1; mask < (1 << n); ++ mask)
for (int last = 0; last < n; ++ last)
if (mask & (1 << last))
for (int now = 0; now < n; ++ now)
if (!(mask & (1 << now)))
if (dp[mask | (1 << now)][now] == 0 || dp[mask | (1 << now)][now] > dp[mask][last] + remain[sir[last]][sir[now]])
{
dp[mask | (1 << now)][now] = dp[mask][last] + remain[sir[last]][sir[now]];
rez[mask | (1 << now)][now] = last;
}
int ans = inf;
int seed;
for (int i = 0; i < n; ++ i)
if (ans > dp[(1 << n) - 1][i])
{
ans = dp[(1 << n) - 1][i];
seed = i;
}
show_solution((1 << n) - 1, seed);
}