Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <string>
- #include <set>
- using namespace std;
- int main() {
- int n, m;
- cin >> n;
- vector<int> v1(n + 1);
- for (int i = 1; i <= n; i++) {
- cin >> v1[i];
- }
- cin >> m;
- vector<int> v2(m + 1);
- for (int i = 1; i <= m; i++) {
- cin >> v2[i];
- }
- vector<vector<int>> dp(n + 1, vector<int>(m + 1));
- vector<vector<pair<int, int>>> last(n + 1, vector<pair<int, int>>(m + 1));
- vector<vector<int>> cur(n + 1, vector<int>(m + 1, -10100));
- dp[0][0] = 0;
- for (int i = 1; i <= n; i++) {
- for (int j = 1; j <= m; j++) {
- if (v1[i] == v2[j]) {
- dp[i][j] = dp[i - 1][j - 1] + 1;
- last[i][j] = make_pair(i - 1, j - 1);
- cur[i][j] = v1[i];
- } else {
- if (dp[i][j - 1] > dp[i - 1][j]) {
- last[i][j] = make_pair(i, j - 1);
- cur[i][j] = -10100;
- dp[i][j] = dp[i][j - 1];
- } else {
- last[i][j] = make_pair(i - 1, j);
- cur[i][j] = -10100;
- dp[i][j] = dp[i - 1][j];
- }
- }
- }
- }
- int k = dp[n][m];
- vector<int> ans;
- pair<int, int> it = make_pair(n, m);
- while (it != make_pair(0, 0)) {
- if (cur[it.first][it.second] != -10100) {
- ans.push_back(cur[it.first][it.second]);
- }
- it = last[it.first][it.second];
- }
- for (int i = 0; i < k; i++) {
- cout << ans[k - 1 - i] << ' ';
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement