← 返回题单

题单练习双序列型DP入门

← 上一题下一题 →

A6971 | $LCIS$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

如果对于所有 $i n$，都有 $a_i a_{i+1}$，则称序列 $a_1, a_2, \ldots, a_n$ 为递增序列。 如果存在一组下标 $1 \leq i_1 i_2 \ldots i_k \leq n$，使得 $a_{i_j} = s_j$，则称序列 $s_1, s_2, \ldots, s_k$ 是序列 $a_1, a_2, \ldots, a_n$ 的子序列。换句话说，序列 $s$ 可以通过从序列 $a$ 中删除某些元素得到。 现在给定两个整数序列。请你找出它们的最长公共递增子序列，即长度最大的递增序列，且该序列同时是两个序列的子序列。

输入格式

第一行包含一个整数 $n$（$1 \leq n \leq 500$），表示第一个序列的长度。 第二行包含 $n$ 个用空格分隔的整数，范围为 $[0, 10^9]$，表示第一个序列的元素。 第三行包含一个整数 $m$（$1 \leq m \leq 500$），表示第二个序列的长度。 第四行包含 $m$ 个用空格分隔的整数，范围为 $[0, 10^9]$，表示第二个序列的元素。

输出格式

第一行输出 $k$，即最长公共递增子序列的长度。 第二行输出该子序列本身，元素之间用空格分隔。如果有多种方案，输出任意一种均可。

输入输出样例

输入 #1

7
2 3 1 6 5 4 6
4
1 3 5 6

输出 #1

3
3 5 6

输入 #2

输出 #2

2
0 1

C++ 编辑器

输入

输出