问题1425--LCS与LIS

1425: LCS与LIS

时间限制: 1 Sec  内存限制: 128 MB
提交: 114  解决: 53
[状态] [讨论版] [提交] [命题人:]
题目描述

LCS(最长公共子序列)是单身,LIS(最长上升子序列)也是单身,于是他们在一起了,变成了LCIS(最长公共上升子序列)o(╯□╰)o。你的任务是求给定两个序列的LCIS的长度,此处上升指的是严格单调递增。

输入

第一行一个正整数T(T <= 50),表示有T组数据。

每组数据输入格式如下:

第一行为俩个正整数NM(N,M<=50),表示俩个序列长度。

第二行N个正整数,表示第一个序列。

第三行M个正整数,表示第二个序列。

所有序列中的元素均<=200。

输出

共输出T行,即每组数据的LCIS的长度。

样例输入 Copy
2
5 5
1 3 2 5 4
1 2 3 5 4
9 11
8 1 2 7 6 3 4 13 5
4 1 2 9 10 3 8 7 13 5 6
样例输出 Copy
3
4
提示

样例解释

第一组数据的LCIS<125><124><135><134>,所以答案为3。

第二组数据的LCIS<12313><1235>,所以答案为4。

来源/分类