习题

#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int __OneWan_2024 = [](){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();
int a[505], b[505];
int dp[505][505], pre[505][505];
int main() {
    int n;
    cin >> n;
    for (int i = 1 ; i <= n ; i++) {
        cin >> a[i];
    }
    int m;
    cin >> m;
    for (int i = 1 ; i <= m ; i++) {
        cin >> b[i];
    }
    int ans = 0, x = 0, y = 0;
    for (int i = 1 ; i <= n ; i++) {
        int res = 0, pos = 0;
        for (int j = 1 ; j <= m ; j++) {
            if (a[i] == b[j]) {
                // 选
                dp[i][j] = res + 1;
                pre[i][j] = pos;
                if (ans < dp[i][j]) {
                    ans = dp[i][j];
                    x = i;
                    y = j;
                }
            } else {
                // 不选
                dp[i][j] = dp[i - 1][j];
                if (b[j] < a[i] && dp[i - 1][j] > res) {
                    res = dp[i - 1][j];
                    pos = j;
                }
            }
        }
    }
    vector<int> r;
    while (ans > 1) {
        r.push_back(b[y]);
        for (int i = x - 1 ; i >= 1 ; i--) {
            if (dp[i][pre[x][y]] == ans - 1 && a[i] == b[pre[x][y]]) {
                y = pre[x][y];
                x = i;
                ans--;
                break;
            }
        }
    }
    if (y > 0) {
        r.push_back(b[y]);
    }
    reverse(begin(r), end(r));
    cout << r.size() << "\n";
    for (auto &x : r) {
        cout << x << " ";
    }
    return 0;
}