TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1035
  • 题目
  • P1035咒语
    限制 : 时间限制 : 2000 MS   空间限制 : 65536 KB
    问题描述

    身为拜月教的高级间谍,你的任务总是逼迫你出生入死。比如这一次,拜月教主就派你跟踪赵灵儿一行,潜入试炼窟底。
    据说试炼窟底藏着五行法术的最高法术:风神,雷神,雪妖,火神,山神的咒语。为了习得这些法术,要付出艰辛的努力,但是回报同样十分丰厚。
    拜月希望你告诉他咒语的长度为多少,于是你偷偷躲在一边,想乘机看看咒语究竟是什么。突然,天空出现了两条非常长的数字串,你抓狂了。究竟哪个才是真正的咒语呢?你突然想到,这两个都不是咒语(不妨称之为伪咒语),而真正的咒语却与他们有着密切的联系。于是你打开拜月亲手给你写的纸条:"The Real Incantation is Their Common Increasing Subsequence of Maximal Possible Length(真的咒语是他们的最长上升公共子序列)"
    "该死的拜月,居然还会E文!"你咒骂着,但为了一家老小的生命,又不得不卖命地算着咒语的长度。

    输入格式

    第一行为1个数N,代表有N组测试数据。
    对于每组测试数据,描述了两条数字串,首先一个数字为一条伪咒语的长度M,接下来M个数描述了伪咒语的内容。

    输出格式

    共N行,每行一个数字,描叙了对应咒语的长度。

    样例输入

    1
    5 1 4 2 5 -12
    4 -12 1 2 4

    样例输出

    2

    提示

    对于100%的数据,有1<=N<=5,1<=M<=500,Ai,Bi在长整型范围内。


    来源  vijos p1624