Cod sursa(job #3265214)

Utilizator Andrei_DumyDumitrescu Andrei-George Andrei_Dumy Data 28 decembrie 2024 08:29:38
Problema Cel mai lung subsir comun Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.03 kb
#include <fstream>
#include <list>

using namespace std;

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


int v[1025], dp[1024][1024];

inline void getArray(const int& n)
{
  for(int i=1; i<=n; i++)
  {
    cin>>v[i];
  }
}

void generateDP(const int& n, const int& m)
{
  int x;

  for(int i=1; i<=m; i++)
  {
    cin>>x;

    for(int j=1; j<=n; j++)
    {
      if(v[j]==x)
        dp[i][j]=max(dp[i-1][j-1]+1, dp[i][j-1]);
      else
        dp[i][j]=max(dp[i-1][j], dp[i][j-1]);
    }
  }
  cout<<dp[m][n]<<"\n";
}

list<int> Seq;

void generateSeq(int j, int i)
{
  while(i!=0 && j!=0)
  {
    if(dp[i-1][j]==dp[i][j] && dp[i][j-1]==dp[i][j])
      i--;
    else if(dp[i-1][j]==dp[i][j])
      i--;
    else if(dp[i][j-1]==dp[i][j])
      j--;
    else
    {
      Seq.push_front(v[j]);
      --i, --j;
    }
  }
}

inline void printSeq()
{
  for(auto e: Seq)
    cout<<e<<" "; 
}

int main()
{
  ios::sync_with_stdio(false);

  int n, m;
  cin>>n>>m;

  getArray(n);
  generateDP(n, m);
  generateSeq(n, m); 
  printSeq();

  return 0;
}