题目描述
KK has two sequences,
Aand
B, and wants to find the
kmultiple longest common subsequence.A sequence
Sis a
kmultiple common subsequence of
Aand
Bif and only if it satisfies the following conditions:
Sis a subsequence of
Aand is a subsequence of
B. (A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.)
The length of
Sis
t × kwhere
tis a nonnegative integer. The first element of
Sis
S[1]. If we divide the sequence into
tgroups with the
i- th group containing
S[(i − 1) × k + j](1 ≤ j ≤ k), for every element
g, it shares the same value with other elements that are in the same group which
gbelongs to.
For example,
[1, 1, 2, 2]is a double common subsequence of
[1, 2, 3, 1, 2, 3, 2]and
[1, 3, 1, 2, 2]. KK wants to know the maximum length of such sequence.
输入
The first line is an integer
T, denoting the number of test cases.
For each test case, the first line are three integers
k, n, m, denoting the kind of subsequence, the length of
A and the length of
B.
The second line are
nintegers
A1∼ An, representing the elements of
A.
The third line are
mintegers
B1∼ Bm, representing the elements of
B.
1 ≤ T ≤ 10 , 1 ≤ k, n, m ≤ 10
3
, 1 ≤ Ai, Bi≤ 10
3
.
输出
For each test case, output a line with the maximum length of
kmultiple common subsequence.
3 1 4 5 1 2 3 4 4 1 3 2 4 2 8 7 1 1 2 2 3 3 4 4 1 2 3 1 2 3 3 3 9 9 1 1 1 2 2 2 3 3 3 1 2 3 1 2 3 1 2 3