Cod sursa(job #2093085)

Utilizator dahaandreiDaha Andrei Codrin dahaandrei Data 22 decembrie 2017 21:42:23
Problema Cel mai lung subsir comun Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 0.75 kb
#include <fstream>
#include <queue>

using namespace std;

ifstream in("cmlsc.in");
ofstream out("cmlsc.out");

int dp[1025][1025];
int v1[1025], v2[1025];
queue <int>coada;
int cnt;
int m, n;

int main(){
  in >> m >> n;

  for (int i = 1; i <= m; ++ i)
    in >> v2[i];
  for (int i = 1; i <= n; ++ i)
    in >> v1[i];


  for (int i = 1; i <= n; ++ i){
    for (int j = 1; j <= m; ++ j){

      dp[i][j] += max(dp[i - 1][j], dp[i][j - 1]);

      if (v1[i] == v2[j]){
        dp[i][j] ++;

        if (dp[i][j] > cnt){
          cnt ++;
          coada.push(v1[i]);
        }
      }
    }
  }

  out << dp[n][m] << '\n';

  while (coada.size()){
    out << coada.front() << " ";
    coada.pop();
  }

  return 0;
}