问题 26066 --新扑克牌游戏

26066: 新扑克牌游戏

时间限制: 1 Sec  内存限制: 128 MB
提交: 49  解决: 24
[提交][状态][讨论版][数据上传:][下载FPS1元][下载测试数据1元][3528kb]

题目描述

非常有创造力的SUKE同学,发明了一种新扑克牌, 其中每一个点数(1..N)5种花色,但是~~~他现在随意做了两副牌, 一共N 种点数, 并按照一定顺序排列,我们不妨设这两幅牌为s1, s1,现在请你求出两个字串的最大匹配(这里的最大匹配的定义:若从一个扑克序列(字符串)s中任意抽取一些点数,将它们仍按在s中的顺序排列成一个新串u,则称us的一个子序列。对于两个扑克序列s1s2,如果存在一个序列u同时成为s1s2的子序列,则称us1s2的公共子序列。SUKE已知两个扑克序列s1s2,求s1s2的最大匹配就是指s1s2最长公共子序列的长度。)

 [任务] 编写一个程序:  从输入文件中读入两个等长的扑克序列;  计算它们的最大匹配;  向输出文件打印你得到的结果。

输入

输入文件中第一行有一个整数N,表示SUKE使用了N种不同的点数,以后将它们编号为1…N的整数。 以下还有两行,每行描述一个扑克序列:包含5N1…N的整数,且每一个整数在对应的序列中正好出现5次。

输出

输出文件中只有一个整数,即两个扑克序列中最大匹配数目。

样例输入

2
1 1 2 2 1 1 2 1 2 2
1 2 2 2 1 1 2 2 1 1

样例输出

7

提示


你或许会用到这条定理(降难度啊!!!):



对于两个串 UV 我们记录出1..nV中所有的位置记录在pos1..n】中这样对于任意的Ui】都可以拆成 posUi】】【5..1】(倒序)五个点,组成一个新的序列C1..25n】。。。然后对C进行一般lis(最长上升序列)


[数据约束和评分方法]

60%
的测试数据中:1<=N
<= 1 000

100%
的测试数据中:1<=N
<= 20 000

来源

[提交][状态]