Pagini recente » Cod sursa (job #1400717) | Cod sursa (job #1249842) | Cod sursa (job #1009269) | Cod sursa (job #1735168) | Cod sursa (job #2833555)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("adn.in");
ofstream fout("adn.out");
const int INF = 1e9;
const int DIM = 18;
const int LEN = 3e4 + 7;
vector <string> s;
int add[DIM][DIM];
int cost[DIM][DIM];
bool ok[DIM];
int pos[DIM];
int phi[LEN];
void get_phi(int x)
{
int k = 0;
int p = s[x].size() - 1;
for(int i = 2; i <= p; ++i)
{
while(k && s[x][k + 1] != s[x][i])
{
k = phi[k];
}
if(s[x][k + 1] == s[x][i])
++k;
phi[i] = k;
}
}
int get_cost(int x, int y)
{
int n = s[x].size() - 1;
int m = s[y].size() - 1;
int k = 0;
for(int i = 1; i <= m; ++i)
{
while(k && s[x][k + 1] != s[y][i])
k = phi[k];
if(s[x][k + 1] == s[y][i])
++k;
if(k == n)
{
k = phi[k];
ok[x] = false;
}
}
return n - k;
}
int dp[(1 << DIM)][DIM];
int from[(1 << DIM)][DIM];
vector <string> res;
void print(int mask, int last)
{
if(from[mask][last] == -1)
{
for(int i = 1; i < res[last].size(); ++i)
fout << res[last][i];
return ;
}
print((mask ^ (1 << last)), from[mask][last]);
int p = add[from[mask][last]][last];
for(int i = res[last].size() - p; i < res[last].size(); ++i)
fout << res[last][i];
}
main()
{
int n;
fin >> n;
s.resize(n);
for(auto& i : s)
{
fin >> i;
i = ' ' + i;
}
sort(s.begin(), s.end());
s.erase(unique(s.begin(), s.end()), s.end());
n = s.size();
for(int i = 0; i < n; ++i)
{
ok[i] = true;
get_phi(i);
for(int j = 0; j < n; ++j)
{
if(i != j)
cost[j][i] = get_cost(i, j);
}
}
int id = -1;
for(int i = 0; i < n; ++i)
{
if(ok[i] == true)
{
res.emplace_back(s[i]);
pos[i] = ++id;
}
}
for(int i = 0; i < n; ++i)
if(ok[i] == true)
for(int j = 1; j < n; ++j)
if(ok[j])
add[pos[i]][pos[j]] = cost[i][j], add[pos[j]][pos[i]] = cost[j][i];
n = id + 1;
for(int i = 0; i < (1 << n); ++i)
for(int j = 0; j < n; ++j)
{
dp[i][j] = INF;
from[i][j] = -1;
}
for(int i = 0; i < n; ++i)
dp[(1 << i)][i] = res[i].size() - 1;
for(int i = 0; i < (1 << n); ++i)
for(int j = 0; j < n; ++j)
if(i & (1 << j))
for(int k = 0; k < n; ++k)
if((i & (1 << k)) && k != j)
if(dp[i][j] > dp[i ^ (1 << j)][k] + add[k][j])
{
dp[i][j] = dp[i ^ (1 << j)][k] + add[k][j];
from[i][j] = k;
}
pair <int, int> best = {INF, 0};
for(int i = 0; i < n; ++i)
best = min(best, {dp[(1 << n) - 1][i], i});
print(((1 << n) - 1), best.second);
}