交叉匹配

发布时间: 2017年6月19日 00:22   时间限制: 1000ms   内存限制: 128M

给定如下规则,请在两个数字串之间进行最多的交叉匹配

1、被匹配的两个数字必须相同,且分别在两个数字串中

2、一个位置上的数字只能匹配一次,一条线代表一个匹配,数字顺序不能改变。

3、每个匹配的连线必须且只能与另一条匹配交叉,且这两条匹配的数字不相等。

[图片][图片][图片][图片]

                       正确匹配                                                         错误匹配                                                      错误匹配

[图片]

第一行有一个数字T(1 <= T <= 20),表示有多少组测试数据。

每一组测试数据有三行。第一行有两个数字NM,分别表示两个数字串的数字个数。第二行有N个数字,表示第一个数字串。第三行有M个数字,表示第二个数字串。注意所有数字(包括NM)均为正整数且不大于1000

输出占一行,每一行输出一组测试数据的最多匹配连线条数。

复制
3
6 6
1 3 1 3 1 3
3 1 3 1 3 1
4 4
1 1 3 3 
1 1 3 3 
12 11
1 2 3 3 2 4 1 5 1 3 5 10
3 1 2 3 2 4 12 1 5 5 3 
6
0
8
1538

old_judge

dzk