Cod sursa(job #2276200)

Utilizator ZappaManIosif Adrian-Mihai ZappaMan Data 4 noiembrie 2018 12:54:11
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.17 kb
#include <cstdio>
#include <cstdlib>
#include <cmath>

using namespace std;

#define MAXN 1025

int dp[MAXN][MAXN];
char n[MAXN], m[MAXN], ret[MAXN];
int nl,ml, bst;

int main() {
  freopen("cmlsc.in", "r", stdin);
  freopen("cmlsc.out", "w", stdout);
  scanf("%d %d",&nl, &ml);
  
  for (int i = 0; i < nl; ++i) {
    scanf("%d",&n[i]);
  }
  
  for (int i = 0; i < ml; ++i) {
    scanf("%d", &m[i]);
  }
  
  for (int i = 0; i <= nl; ++i) {
    dp[i][0] = 0;
  }
  
  
  for (int i = 0; i <= ml; ++i) {
    dp[0][i] = 0;
  }
  
  bst = 0;
  
  for (int i = 1; i <= nl; ++i) {
    for (int j = 1; j <= ml; ++j) {
      if (n[i - 1] == m[j - 1]) {
        dp[i][j] = 1 + dp[i-1][j-1];
      } else {
        dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
      }
    }
  }
  
  int i = nl;
  int j = ml;
  
  while (i > 0 && j > 0) {
    if (dp[i][j] == dp[i][j-1]) {
      j -= 1;
    } else if (dp[i][j] == dp[i-1][j]) {
      i -= 1;
    } else {
      ret[bst++] = n[i-1];
      i -= 1;
      j -= 1;
    }
  }
  
  printf("%d\n",dp[nl][ml]);
  for (int i = bst - 1; i >= 0; --i) {
    printf("%d ",ret[i]);
  }
  
  
  return 0;
}