Cod sursa(job #2412269)

Utilizator AlexPop28Pop Alex-Nicolae AlexPop28 Data 21 aprilie 2019 21:36:33
Problema ADN Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.38 kb
#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;
}