Pagini recente » Borderou de evaluare (job #2013740) | Borderou de evaluare (job #689097) | Borderou de evaluare (job #2445586) | Borderou de evaluare (job #2011605) | Cod sursa (job #2412269)
#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'
using namespace std;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long long ll;
typedef unsigned long long ull;
template<class T> bool uin(T &a, T b) {return (a < b ? false : (a = b, true));}
template<class T> bool uax(T &a, T b) {return (a > b ? false : (a = b, true));}
ifstream f("adn.in");
ofstream g("adn.out");
const int LMAX = 30005;
const int NMAX = 20;
int n;
int cost[NMAX][NMAX];
int dp[(1 << NMAX)][NMAX];
int from[(1 << NMAX)][NMAX];
string a[NMAX];
int pi[LMAX];
void read() {
f >> n;
for (int i = 0; i <= n; ++i) {
getline(f, a[i]);
a[i] = " " + a[i];
}
}
void computePi(const string &s) {
memset(pi, 0, sizeof(pi));
int k = 0;
for (int i = 2; i < (int)s.length(); ++i) {
while (k && s[i] != s[k + 1]) {
k = pi[k];
}
if (s[i] == s[k + 1]) {
++k;
}
pi[i] = k;
}
}
int find(const string &s, const string &t) {
int k = 0;
for (int i = 1; i < (int)t.length(); ++i) {
while (k && t[i] != s[k + 1]) {
k = pi[k];
}
if (t[i] == s[k + 1]) {
++k;
}
if (k == (int)s.length() - 1) {
return -1;
}
}
return k;
}
void removeIncluded() {
for (int i = 1; i <= n; ++i) {
computePi(a[i]);
for (int j = 1; j <= n; ++j) {
if (i == j || a[j] == "del") {
continue;
}
if (find(a[i], a[j]) == -1) {
a[i] = "del";
break;
}
}
}
for (int i = 1; i <= n; ++i) {
if (a[i] != "del") {
continue;
}
for (int j = n; j >= i + 1; --j) {
if (a[j] != "del") {
swap(a[i], a[j]);
break;
}
}
if (a[i] == "del") {
n = i - 1;
}
}
}
void getCosts() {
for (int i = 1; i <= n; ++i) {
computePi(a[i]);
for (int j = 1; j <= n; ++j) {
if (i == j) {
continue;
}
cost[j][i] = find(a[i], a[j]);
}
}
}
void getMinCostPath() {
for (int mask = 1; mask < (1 << n); ++mask) {
vector<int> v;
for (int bit = 0; (1 << bit) <= mask; ++bit) {
if (mask & (1 << bit)) {
v.push_back(bit + 1);
}
}
for (int last : v) {
for (int prev : v) {
if (last == prev) {
continue;
}
int old_mask = mask ^ (1 << (last - 1));
if (uax(dp[mask][last], dp[old_mask][prev] + cost[prev][last])) {
from[mask][last] = prev;
}
}
}
}
}
void getAns() {
int last = 0;
int max_cost = 0;
for (int i = 1; i <= n; ++i) {
if (uax(max_cost, dp[(1 << n) - 1][i])) {
last = i;
}
}
int right = a[last].size() - 1;
int mask = (1 << n) - 1;
int prev = from[mask][last];
string ans = "";
while (mask) {
mask ^= (1 << (last - 1));
for (int i = right; i >= 1; --i) {
ans += a[last][i];
}
right = a[prev].size() - cost[prev][last] - 1;
last = prev;
prev = from[mask][last];
}
reverse(ans.begin(), ans.end());
g << ans << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL_DEFINE
freopen(".in", "r", stdin);
#endif
read();
removeIncluded();
getCosts();
getMinCostPath();
getAns();
f.close();
g.close();
#ifdef LOCAL_DEFINE
cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
#endif
return 0;
}