比赛场次 | 223 |
---|---|
比赛名称 | 20110928 |
比赛状态 | 已结束比赛成绩 |
开始时间 | 2013-11-05 19:00:00 |
结束时间 | 2013-11-05 22:00:00 |
开放分组 | 全部用户 |
注释介绍 |
题目名称 | 交错匹配 |
---|---|
输入输出 | crossa.in/out |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试点数 | 10 简单对比 |
用户 | 结果 | 时间 | 内存 | 得分 |
---|---|---|---|---|
C语言入门 | AAAAAAAAAA | 0.833 s | 0.32 MiB | 100 |
cstdio | WAWAWAAAAA | 0.006 s | 0.55 MiB | 70 |
digital-T | WWWAWAAWWA | 0.003 s | 0.32 MiB | 40 |
赵赵赵 | AWWAWWWWAW | 0.010 s | 25.37 MiB | 30 |
【问题描述】
有两行自然数, UP[1..N] , DOWN[1..M] ,如果 UP[I]=DOWN[J]=K ,那么上行的第 I 个位置的数就可以跟下行的第 J 个位置的数连一条线,称为一条 K 匹配,但是 同一个位置 的数最多只能连一条线。另外,每个 K 匹配都 必须且至多 跟一个 L 匹配相交且 K ≠ L !现在要求一个最大的匹配数。
【输入格式】
第一行有两个正整数 N 和 M 。第二行 N 个 UP 的自然数,第三行 M 个 DOWN 的自然数。其中 0<N 、 M<=200 , UP 、 DOWN 的数都不超过 32767 。
【输出格式】
最大匹配数 。
【输入输出样例1】
输入:
crossa.in 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
输出:
crossa.out 8
【输入输出样例2】
输入:
crossa.in 4 4 1 1 3 3 1 1 3 3
输出:
crossa.out 0