Raslboyy

1790

Sep 5th, 2019
168
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.90 KB | None | 0 0
  1. #include <iostream>
  2. #include <fstream>
  3. #include <algorithm>
  4. #include <vector>
  5.  
  6. using namespace std;
  7.  
  8. int main() {
  9.     ifstream fin("input.txt");
  10.     ofstream fout("output.txt");
  11.  
  12.     int n, m;
  13.     fin >> n;
  14.     vector<int> A(n);
  15.     for (int i = 0; i < n; i++) fin >> A[i];
  16.     fin >> m;
  17.     vector<int> B(m);
  18.     for (int i = 0; i < m; i++) fin >> B[i];
  19.     vector<vector<int>> dp(n + 1, vector<int>(m + 1));
  20.     for (int i = 1; i <= n; i++)
  21.         for (int j = 1; j <= m; j++) {
  22.             if (A[i-1] == B[j-1])
  23.                 dp[i][j] = dp[i-1][j-1] + 1;
  24.             else
  25.                 dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
  26.         }
  27.  
  28.     int a = n; int b = m;
  29.     vector<int> answ;
  30.     while (a > 0 && b > 0) {
  31.         if (A[a - 1] == B[b - 1]) {
  32.             answ.push_back(A[a - 1]);
  33.             a--; b--;
  34.         }
  35.         else if (dp[a][b] == dp[a][b - 1])
  36.             b--;
  37.         else
  38.             a--;
  39.     }
  40.     for (int i = answ.size() - 1; i >= 0; i--) fout << answ[i] << " ";
  41.  
  42.     fin.close();
  43.     fout.close();
  44.     return 0;
  45. }
Advertisement
Add Comment
Please, Sign In to add comment