提交: 16 解决: 5

[状态] [讨论版] [提交] [命题人:]

题目描述

KK has two sequences,*A* and *B*, and wants to find the* k* multiple longest common subsequence.A sequence **S **is a **k** multiple common subsequence of *A* and *B* if and only if it satisfies the following conditions:

*S* is a subsequence of *A* and 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*S* is *t × k* where *t* is a nonnegative integer. The first element of *S* is *S[1]*. If we divide the sequence into *t* groups 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 *g* belongs 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 length of

For example,

输入

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** n** integers *A*_{1} ∼ A_{n}, representing the elements of *A*.

The third line are* m* integers *B*_{1} ∼ B_{m}, representing the elements of **B**.

*1 ≤ T ≤ 10 , 1 ≤ k, n, m ≤ 10*^{3}* , 1 ≤ A*_{i}, B_{i} ≤ 10^{3}*.*

For each test case, the first line are three integers

The second line are

The third line are

输出

For each test case, output a line with the maximum length of *k* multiple common subsequence.

样例输入
Copy

```
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
```

样例输出 Copy

```
3
4
3
```

来源/分类