Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define mp make_pair
- #define sz size()
- #define ull unsigned long long
- #define ll long long
- #define ld long double
- #define all(x) (x).begin(), (x).end()
- #define pb push_back
- #define sc second
- #define fs first
- using namespace std;
- const ll INF = 2000000000000000000;
- vector<int> ans;
- int a[1001], b[1001], dp[1001][1001];
- int min3(int a, int b, int c) {
- return min(min(a, b), c);
- }
- void restore(int i, int j) {
- if (i >= 0 && j >= 0) {
- if (a[i] == b[j]) {
- ans.pb(a[i]);
- restore(i - 1, j - 1);
- } else if (dp[i][j] == dp[i - 1][j])
- restore(i - 1, j);
- else
- restore(i, j - 1);
- }
- }
- int main() {
- freopen("input.txt", "r", stdin);
- freopen("output.txt", "w", stdout);
- int n;
- cin >> n;
- for (int i = 0; i<n; i++)
- cin >> a[i];
- int m;
- cin >> m;
- for (int i = 0; i<m; i++)
- cin >> b[i];
- memset(dp, 0, sizeof(dp));
- int s = 1000000000;
- for (int i = 0; i<m; i++) {
- if (a[0] == b[i]) {
- s = i;
- break;
- }
- }
- for (int i = s; i<m; i++)
- dp[0][i] = 1;
- s = 1000000000;
- for (int i = 0; i<n; i++) {
- if (b[0] == a[i]) {
- s = i;
- break;
- }
- }
- for (int i = s; i<n; i++)
- dp[i][0] = 1;
- for (int i = 1; i<n; i++)
- for (int j = 1; j<m; j++) {
- if (a[i] == b[j])
- dp[i][j] = dp[i - 1][j - 1] + 1;
- else
- dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
- }
- //cout << dp[n - 1][m - 1] << "\n";
- restore(n - 1, m - 1);
- reverse(all(ans));
- for (int i = 0; i<ans.size(); i++)
- cout << ans[i] << " ";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement