Advertisement
Guest User

Untitled

a guest
Nov 16th, 2018
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.58 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. int main()
  6. {
  7.     int n;
  8.     cin >> n;
  9.     vector <int> a(n + 1);
  10.     for (int i = 1; i <= n; i++)
  11.         cin >> a[i];
  12.     int m;
  13.     cin >> m;
  14.     vector <int> b(m + 1);
  15.     for (int i = 1; i <= m; i++)
  16.         cin >> b[i];
  17.     vector <int> pr(m + 1, -1);
  18.     vector <vector <int> > dp(n + 1, vector<int>(m + 1));
  19.     for (int i = 1; i <= n; i++)
  20.     {
  21.         int p = 0;
  22.         int ind = 0;
  23.         for (int j = 1; j <= m; j++)
  24.         {
  25.             if (a[i] != b[j])
  26.                 dp[i][j] = dp[i - 1][j];
  27.             if (a[i] == b[j])
  28.                 if (p + 1 > dp[i - 1][j])
  29.                 {
  30.                     pr[j] = ind;
  31.                     dp[i][j] = p + 1;
  32.                 }
  33.                 else
  34.                     dp[i][j] = dp[i - 1][j];
  35.             if (dp[i][j] > p && b[j] < a[i])
  36.             {
  37.                 p = dp[i][j];
  38.                 ind = j;
  39.             }
  40.         }
  41.     }
  42.     /*for (int i = 1; i <= n; ++i) {
  43.         for (int j = 1; j <= m; ++j)
  44.             cout << dp[i][j] << " ";
  45.         cout << '\n';
  46.     }
  47.     for (int j = 1; j <= m; ++j)
  48.         cout << pr[j] << " "; */
  49.     int pos = 0;
  50.     for (int i = 1; i <= m; i++)
  51.     {
  52.         if (dp[n][i] > dp[n][pos])
  53.             pos = i;
  54.     }
  55.     vector <int> ot;
  56.     while (pr[pos] != -1)
  57.     {
  58.         ot.push_back(b[pos]);
  59.         pos = pr[pos];
  60.     }
  61.     //ot.push_back(b[pos]);
  62.     cout << ot.size() << endl;
  63.     for (auto it = ot.rbegin(); it != ot.rend(); it++)
  64.         cout << *it << " ";
  65.     system("pause");
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement