Cod sursa(job #1393890)

Utilizator paul-gPaul Grigoras paul-g Data 19 martie 2015 20:34:45
Problema Cel mai lung subsir comun Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <vector>
#include <deque>

using namespace std;

int main(int argc, char *argv[])
{
  ifstream f{"cmlsc.in"};
  ofstream g{"cmlsc.out"};

  int m, n;
  f >> m >> n;

  vector<int> a(m), b(n);

  for (int i = 0; i < m; ++i)
  {
    f >> a[i];
  }

  for (int i = 0; i < n; ++i)
  {
    f >> b[i];
  }

  int best[m + 1][n + 1];

  for (int i = 0; i <= m; ++i)
  {
    for (int j = 0; j <= n; ++j)
    {
      best[i][j] = 0;
    }
  }

  for (int i = 1; i <= m; ++i)
  {
    for (int j = 1; j <= n; ++j)
    {
      best[i][j] = max(best[i - 1][j], best[i][j - 1]);
      if (a[i - 1] == b[j - 1])
        best[i][j] = max(1 + best[i - 1][j - 1],
            best[i][j]);
    }
  }

  g << best[m][n] << endl;
  int i = m;
  int j = n;
  deque<int> sol;
  while (i != 0 && j != 0) {
    if (best[i - 1][j - 1] +1 == best[i][j]) {
      sol.push_front(a[i - 1]);
      i--;
      j--;
    } else if (best[i - 1][j] == best[i][j])
      i--;
    else 
      j--;
  }

  for (auto i : sol) {
    g << i << " ";
  }

  return 0;
}