P96878

5.1.3Musical Themes 乐曲主题

难度 未定
讨论 统计 0通过 5提交 0%通过率 旧版界面
时间限制 1 秒 内存限制 128 MB

题目描述

我们用 N(1 <= N <=5000)个音符的序列来表示一首乐曲,每个音符都是 1..88 范围内的整数,每个数表示钢琴上的一个键.很不幸这种表示旋律的方法忽略了音符的时值,但这项编程任务是关于音高的,与时值无关.许多作曲家围绕一个重复出现的“主题”来构建乐曲.在我们的乐曲表示法中,“主题”是整个音符序列的一个子序列,它需要满足如下条件:

长度至少为 5 个音符

在乐曲中重复出现(可能经过转调,见下)

重复出现的同一主题不能重叠

“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值.

给定一段乐曲,计算其中最长主题的长度(即音符数).

本题时限为 1 秒钟!

输入

输出文件的第一行包含整数 N.下面的每一行(最后一行可能除外)包含 20 个整数,表示音符序列.最后一行可能少于 20 个音符.

输出

输出文件应只含一个整数,即最长主题的长度.如果乐曲中没有主题,那么输出 0.

样例

样例 1
输入
30 
25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18 
82 78 74 70 66 67 64 60 65 80
输出
5 
(这个长度为 5 的主题是输入文件中第一行的最后 5 个音符和第二行开头 5 个音符)

来源

USACO

Tab 缩进 · 提交后可在下方查看评测状态
请先登录后再提交