Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2017
59
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.61 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5. #include <set>
  6.  
  7. using namespace std;
  8.  
  9. int main() {
  10.     int n, m;
  11.     cin >> n;
  12.     vector<int> v1(n + 1);
  13.     for (int i = 1; i <= n; i++) {
  14.         cin >> v1[i];
  15.     }
  16.     cin >> m;
  17.     vector<int> v2(m + 1);
  18.     for (int i = 1; i <= m; i++) {
  19.         cin >> v2[i];
  20.     }
  21.     vector<vector<int>> dp(n + 1, vector<int>(m + 1));
  22.     vector<vector<pair<int, int>>> last(n + 1, vector<pair<int, int>>(m + 1));
  23.     vector<vector<int>> cur(n + 1, vector<int>(m + 1, -10100));
  24.     dp[0][0] = 0;
  25.     for (int i = 1; i <= n; i++) {
  26.         for (int j = 1; j <= m; j++) {
  27.             if (v1[i] == v2[j]) {
  28.                 dp[i][j] = dp[i - 1][j - 1] + 1;
  29.                 last[i][j] = make_pair(i - 1, j - 1);
  30.                 cur[i][j] = v1[i];
  31.             } else {
  32.                 if (dp[i][j - 1] > dp[i - 1][j]) {
  33.                     last[i][j] = make_pair(i, j - 1);
  34.                     cur[i][j] = -10100;
  35.                     dp[i][j] = dp[i][j - 1];
  36.                 } else {
  37.                     last[i][j] = make_pair(i - 1, j);
  38.                     cur[i][j] = -10100;
  39.                     dp[i][j] = dp[i - 1][j];
  40.                 }
  41.             }
  42.         }
  43.     }
  44.     int k = dp[n][m];
  45.     vector<int> ans;
  46.     pair<int, int> it = make_pair(n, m);
  47.     while (it != make_pair(0, 0)) {
  48.         if (cur[it.first][it.second] != -10100) {
  49.             ans.push_back(cur[it.first][it.second]);
  50.         }
  51.         it = last[it.first][it.second];
  52.     }
  53.     for (int i = 0; i < k; i++) {
  54.         cout << ans[k - 1 - i] << ' ';
  55.     }
  56. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement