/ Vijos / 题库 /

删数

删数

时间限制:1秒  内存限制:256M


【问题描述】

  整数序列 \(A\) 和 \(B\) 都是 \(1,2,…,n\) 全排列。

  每次可以选择两个排列中的一个数删除。

  那么要想把两个排列变成一样的,最少需要删除多少个数?

  注意:最后得到的两个相同的排列中的元素在原全排列中的相对位置不变。

【输入格式】

  第一行是整数 \(n\)。接下来两行,每行分别包含 \(n\) 个 \(1..n\) 范围内的整数,分别表示序列 \(A\) 和序列 \(B\)。同行相邻整数间用一个空格隔开。

【输出格式】

  一行一个整数,表示最少需要删除的数的个数。

【输入输出样例1】

 Input

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

 Output

6

【样例1解释】

  把两个排列中的 2、1和6删除,于是两个序列都变成了 3 5 4。

【输入输出样例2】

 Input

10
1 2 3 4 5 6 7 8 9 10
2 6 7 3 8 5 4 9 10 1

 Output

8

【数据说明】

  对于 \(80\%\) 的数据 \(1≤n≤5000\)。
  对于 \(100\%\) 的数据 \(1≤n≤200000\)。

【来源】

  Mr.he

信息

ID
3083
难度
9
分类
动态规划 | LCSLIS 点击显示
标签
(无)
递交数
2
已通过
1
通过率
50%
被复制
1
上传者