Cod sursa(job #1005830)

Utilizator bigdoggMic Matei bigdogg Data 5 octombrie 2013 21:48:55
Problema Cel mai lung subsir comun Scor 20
Compilator cpp Status done
Runda Arhiva educationala Marime 0.97 kb
#include <fstream>
#include <cstdint>

using namespace std;

const int MAX_SEQ = 1024;

uint8_t a[MAX_SEQ], b[MAX_SEQ];
uint16_t subprobs[MAX_SEQ][MAX_SEQ];

ofstream out("cmlsc.out");

void printLSC(int i, int j);

int main(int argc, char *argv[])
{
  ifstream in("cmlsc.in");
  int m, n;  in >> m >> n;

  for(int i = 0; i < m; ++i) in >> a[i];
  for(int i = 0; i < n; ++i) in >> b[i];

  for(int i = 1; i <= m; ++i)
    for(int j = 1; j <= n; ++j)
      if(a[i - 1] == b[j - 1]) subprobs[i][j] = subprobs[i - 1][j - 1] + 1;
      else subprobs[i][j] = subprobs[i][j - 1] > subprobs[i - 1][j] ?
        subprobs[i][j - 1] : subprobs[i - 1][j];

  out << subprobs[m][n] << endl;
  printLSC(m, n);
  out << endl;

  return 0;
}

void printLSC(int i, int j)
{
  if(i == 0 || j == 0) return;

  if(subprobs[i][j] == subprobs[i - 1][j]){ printLSC(i - 1, j); return; }
  if(subprobs[i][j] == subprobs[i][j - 1]){ printLSC(i, j - 1); return; }

  printLSC(i - 1, j - 1);
  out << a[i - 1] << ' ';
}