跳至正文
题库3981
#3981

1306. 最长公共子上升序列

查看题目操作

1306. 最长公共子上升序列

题目描述

给定两个整数序列,求它们的最长公共上升子序列。 长度为 KK 的序列 S1,…,SKS_1,\ldots,S_K 是 A1,…,AMA_1,\ldots,A_M 的上升子序列,当且仅当存在 1≤i1<⋯<iK≤M1\le i_1<\cdots<i_K\le M,使所有 1≤j≤K1\le j\le K 都满足 Sj=AijS_j=A_{i_j},且所有 1≤j<K1\le j<K 满足 Sj<Sj+1S_j<S_{j+1}。 公共子序列必须同时是两个输入序列的子序列。

输入格式

每个序列用两行表示,第一行是长度 M(1≤M≤500)M(1 \le M \le 500),第二行是该序列的M个整数 Ai(−231≤Ai<231)A_i(-2^{31} \le A_i < 2^{31})。

输出格式

在第一行,输出两个序列的最长上升公共子序列的长度 LL。在第二行,输出该子序列。如果有不止一个符合条件的子序列,则输出任何一个即可;L=0 时第二行为空行。不得输出额外内容。

5
1 4 2 5 -12
4
-12 1 2 4
2
1 4

提示

经典算法Baidu搜索,深刻体会。

来源

一本通在线评测 ybtbas-1306