测评会员优惠活动进行中 · 开通 VIP,有效期内测评不限次 VIP 优惠中 · 测评不限次 立即查看

A7015. 数字连线游戏

编程题 普及-

题目描述

老师在黑板上写了两行数字。
第一行数字记为 $A$,一共有 $n$ 个。
第二行数字记为 $B$,一共有 $m$ 个。

现在我们要玩一个“连线游戏”,规则如下:

1. **找相同**:你只能用直线连接两个**数字相同**的数(一个在第一行,一个在第二行)。
2. **不打结**:为了美观,你画的所有连线**不能相交**(不能在中间交叉)。
3. **一对一**:每个数字最多只能连出一口线。

请你算一算,最多能画出多少条不相交的连线?

输入格式

输入共 3 行。
第一行包含两个整数 $n$ 和 $m$,分别表示第一行和第二行数字的个数。
第二行包含 $n$ 个整数,表示第一行的数字序列 $A$。
第三行包含 $m$ 个整数,表示第二行的数字序列 $B$。

输出格式

输出一个整数,表示最多能画出的连线数量。

输入输出样例

输入 #1
3 3
1 4 2
1 2 4
输出 #1
2
输入 #2
5 6
2 5 1 2 5
10 5 2 1 5 2
输出 #2
3

说明/提示

### 数据范围

* $1 \le n, m \le 1000$
* $1 \le A_i, B_j \le 2000$

### 样例解释

**样例 1 解释:**
我们可以画出 2 条不相交的线:

* 第一行第 1 个数 1 和第二行第 1 个数 1 相连。
* 第一行第 2 个数 4 和第二行第 3 个数 4 相连。
*(注意:虽然都有数字 2,但如果连了 44,再连 22,线条就会交叉,这是不允许的。)*

**样例 2 解释:**
一种最优的连法是:

* $A[2]$ 的 5 连 $B[2]$ 的 5
* $A[3]$ 的 1 连 $B[4]$ 的 1
* $A[5]$ 的 5 连 $B[5]$ 的 5
共 3 条线,且互不相交。
上一题 去做题 下一题