普及⏱ 1000ms💾 256MB#P5139🏷️ 动态规划

题目描述

马拉松接力赛有两条检录线,各自按时间顺序记下了一批参赛者号码。 若能从两条记录中各挑出若干号码(保持各自顺序),使号码相同且严格递增,就构成一支"公共接力队"。

求最长的公共接力队:第一行输出长度,第二行输出一组合法号码。 若有多个可行答案,输出任意一个即可(本题数据保证最长公共上升子序列唯一)。

输入格式

共四行:第一行是第一条记录的长度 $M$,第二行为 $M$ 个整数; 第三行是第二条记录的长度 $N$,第四行为 $N$ 个整数。

输出格式

第一行一个整数 $L$:最长公共上升子序列的长度; 第二行 $L$ 个整数,用空格分开:该子序列(数据保证唯一)。

数据范围

$$1 \le M, N \le 500$$
,元素绝对值不超过 $10^9$;数据保证最长公共上升子序列唯一。

样例输入 #1
3
1 4 2
3
-12 1 4
样例输出 #1
2
1 4
样例输入 #2
2
7 8
2
7 8
样例输出 #2
2
7 8