P2743 [USACO5.1]乐曲主题Musical Themes

    • 471通过
    • 1.6K提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 高性能
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    我们用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
    输出样例#1: 复制
    5

    说明

    题目翻译来自NOCOW。

    USACO Training Section 5.1

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。