#include <bits/stdc++.h>
using namespace std;

int n, m;
int dp[510][510];   // dp[i][j] a1~ai,b1~bj且以bj结尾的LCIS长度
int pre[510][510];  // pre[i][j] 记录在匹配 a[i]==b[j] 时,b 的前驱位置
int a[510], b[510];
vector<int> path;

int LCIS() {
	if (n == 0 || m == 0) return 0;
	int ans = 0;
	int x = 0, y = 0; // 记录最大 dp 值的位置
	
	for (int i = 1; i <= n; i++) 
	{
		for (int j = 1; j <= m; j++) 
		{
			if (a[i] == b[j]) 
			{
				int mx = 0, mx_prek = 0;
				for (int k = 1; k < j; k++) 
				{
					if (b[k] < b[j] && dp[i - 1][k] > mx) 
					{
						mx = dp[i - 1][k];
						mx_prek = k;
					}
				}
				dp[i][j] = mx + 1;
				pre[i][j] = mx_prek;
			}
			else 
				dp[i][j] = dp[i - 1][j];
			if (dp[i][j] > ans) 
			{
				ans = dp[i][j];
				x = i, y = j; // 记录最大值的位置,方便一会从x,y往前回溯路径
			}
		}
	}
	
	// 回溯路径
	while (x > 0 && y > 0) 
	{
		if (a[x] == b[y] && dp[x][y] > 0) 
		{
			path.push_back(a[x]);
			y = pre[x][y]; // 跳到前一个匹配的位置
			x--;           // 继续往前找
		} 
		else x--; // 不匹配就往前走
	}
	reverse(path.begin(), path.end());
	return ans;
}

int main() 
{
	freopen("LCIS.in", "r", stdin);
	freopen("LCIS.out", "w", stdout);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	cin >> m;
	for (int i = 1; i <= m; i++) cin >> b[i];
	
	int len = LCIS();
	cout << len << endl;
	for (int i = 0; i < path.size(); i++)
		cout << path[i] << " ";
	return 0;
}

0 条评论

目前还没有评论...