Cod sursa(job #2771710)

Utilizator Razvan48Capatina Razvan Nicolae Razvan48 Data 28 august 2021 19:42:05
Problema ADN Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.49 kb
#include <fstream>
#include <cstring>
#include <vector>
#include <string>

using namespace std;

const int NMAX = 18;
const int LMAX = 30001;
const int INF  = 1000000;

string cuvinte[NMAX];

string s;
int prefix[5 + 2 * LMAX];

bool inclus[1 + NMAX];

vector<pair<int, int>> graf[NMAX];

int dp[1 << NMAX][NMAX];
pair<int, int> last[1 << NMAX][NMAX];

void kmp(int i, int j)
{
  memset(prefix, 0, sizeof(prefix));
  s = ' ' + cuvinte[i] + '$' + cuvinte[j];

  int pi = 0;

  for (int l = 2; l < s.size(); l++)
  {
    while (pi > 0 && s[l] != s[pi + 1])
      pi = prefix[pi];

    if (s[l] == s[pi + 1])
      pi++;

    prefix[l] = pi;

    if (pi == cuvinte[i].size())
      inclus[i] = true;
  }

  graf[i].emplace_back(make_pair(j, cuvinte[i].size() - prefix[s.size() - 1]));
}

string makeSol(int bitMask, int nod)
{
  if (bitMask == 0)
    return "";

  string s = makeSol(bitMask - (1 << nod), last[bitMask][nod].first);

  for (int i = cuvinte[nod].size() - last[bitMask][nod].second; i < cuvinte[nod].size(); i++)
    s += cuvinte[nod][i];

  return s;
}

int main()
{
  ifstream in("adn.in");
  ofstream out("adn.out");

  int n;
  in >> n;

  for (int i = 0; i < n; i++)
    in >> cuvinte[i];

  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
      if (i != j)
        kmp(i, j);

  for (int bitMask = 0; bitMask < (1 << n); bitMask++)
    for (int nod = 0; nod < n; nod++)
      dp[bitMask][nod] = INF;
  for (int nod = 0; nod < n; nod++)
  {
    dp[1 << nod][nod] = cuvinte[nod].size();
    last[1 << nod][nod] = make_pair(-1, cuvinte[nod].size());
  }

  for (int bitMask = 0; bitMask < (1 << n); bitMask++)
    for (int nod = 0; nod < n; nod++)
      if (!inclus[nod] && (bitMask & (1 << nod)) != 0)
        for (auto& vecin : graf[nod])
          if (!inclus[vecin.first] && (bitMask & (1 << vecin.first)) != 0)
            if (dp[bitMask][nod] > dp[bitMask - (1 << nod)][vecin.first] + vecin.second)
            {
              dp[bitMask][nod] = dp[bitMask - (1 << nod)][vecin.first] + vecin.second;
              last[bitMask][nod] = vecin;
            }

  int sol = INF;
  int solMask = (1 << n) - 1;
  int solNod = -1;

  for (int i = 0; i < n; i++)
    if (inclus[i])
      solMask -= (1 << i);

  for (int i = 0; i < n; i++)
    if (!inclus[i] && sol > dp[solMask][i])
    {
      sol = min(sol, dp[solMask][i]);
      solNod = i;
    }

  out << makeSol(solMask, solNod) << '\n';

  return 0;
}