P3858.第3题-不想交线的条数

1000ms

Difficulty: 5

所属公司 : 网易

算法与标签>动态规划

题目内容

在两条独立的水平线上按给定的顺序写下 $nums1$ 和 $nums2$ 中的整数。

现在，可以绘制一些连接两个数字 $nums1[i]$ 和 $nums2[j]$ 的直线，这些直线需要同时满足满足： $nums1[i]==nums2[j]$

且绘制的直线不与任何其他连线(非水平线)相交。

请注意，连线即使在端点也不能相交：每个数字只能属于一条连线。

以这种方法绘制线条，并返回可以绘制的最大连线数。

$1 <=nums1.length,nums2.length<=2000$

$1 <= nums1[i]，nums2[i]<= 2000$

每组输入为两行，表示 $nums1$ 和 $nums2$ 两个数组。每行有 $n+1$ 个数字，数字间用空格分开，第一个数字表示数组个数 $n$ ，后面跟 $n$ 个数字；如 $2$ $23$ ，表示数组有 $2$ 个元素，元素值为 $2$ 和 $3$

输出最多能绘制不想交线的条数。

输入

3 1 4 2
3 1 2 4

输出

输入

5 1 2 2 3 4
5 2 2 2 4 1

输出

输入

预期输出（选填）