Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- int main()
- {
- int n;
- cin >> n;
- vector <int> a(n + 1);
- for (int i = 1; i <= n; i++)
- cin >> a[i];
- int m;
- cin >> m;
- vector <int> b(m + 1);
- for (int i = 1; i <= m; i++)
- cin >> b[i];
- vector <int> pr(m + 1, -1);
- vector <vector <int> > dp(n + 1, vector<int>(m + 1));
- for (int i = 1; i <= n; i++)
- {
- int p = 0;
- int ind = 0;
- for (int j = 1; j <= m; j++)
- {
- if (a[i] != b[j])
- dp[i][j] = dp[i - 1][j];
- if (a[i] == b[j])
- if (p + 1 > dp[i - 1][j])
- {
- pr[j] = ind;
- dp[i][j] = p + 1;
- }
- else
- dp[i][j] = dp[i - 1][j];
- if (dp[i][j] > p && b[j] < a[i])
- {
- p = dp[i][j];
- ind = j;
- }
- }
- }
- /*for (int i = 1; i <= n; ++i) {
- for (int j = 1; j <= m; ++j)
- cout << dp[i][j] << " ";
- cout << '\n';
- }
- for (int j = 1; j <= m; ++j)
- cout << pr[j] << " "; */
- int pos = 0;
- for (int i = 1; i <= m; i++)
- {
- if (dp[n][i] > dp[n][pos])
- pos = i;
- }
- vector <int> ot;
- while (pr[pos] != -1)
- {
- ot.push_back(b[pos]);
- pos = pr[pos];
- }
- //ot.push_back(b[pos]);
- cout << ot.size() << endl;
- for (auto it = ot.rbegin(); it != ot.rend(); it++)
- cout << *it << " ";
- system("pause");
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement