Cod sursa(job #2855218)

Utilizator MihneaCadar101Cadar Mihnea MihneaCadar101 Data 22 februarie 2022 11:08:07
Problema Cel mai lung subsir comun Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.74 kb
#include <bits/stdc++.h>
using namespace std;

int n, m, v1[1050], v2[1050], sir[1050], d[1050][1050];
int main()
{
   cin >> n >> m;
   for (int i = 1; i <= n; ++i)
      cin >> v1[i];

   for (int i = 1; i <= m; ++i)
      cin >> v2[i];

   for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= m; ++j) {
         if (v1[i] == v1[j])
            dp[i][j] = dp[i - 1][j - 1] + 1;
         else
            dp[i][j] = max(dp[i][j - 1], dp[i - 1]);
      }
   }

   int i = n, j = m;
   while (i && j) {
      if (v1[i] == v2[j]) {
         sir[maxi] = v1[i];
         --maxi;
         --i;
         --j;
      }
      else if (dp[i][j - 1] > dp[i - 1][j])
         --j;
      else
         --i;
   }

   return 0;
}