题目地址：洛谷：【P2743】[USACO5.1]乐曲主题Musical Themes – 洛谷

题目描述

我们用N(1 <= N <=5000)个音符的序列来表示一首乐曲，每个音符都是1..88范围内的整数，每个数表示钢琴上的一个键。很不幸这种表示旋律的方法忽略了音符的时值，但这项编程任务是关于音高的，与时值无关。
许多作曲家围绕一个重复出现的“主题”来构建乐曲。在我们的乐曲表示法中，“主题”是整个音符序列的一个子串，它需要满足如下条件：
⒈长度至少为5个音符
⒉在乐曲中重复出现(可能经过转调，见下)
⒊重复出现的同一主题不能有公共部分。
“转调”的意思是主题序列中每个音符都被加上或减去了同一个整数值。 给定一段乐曲，计算其中最长主题的长度(即音符数)。

题意简述

求序列中两段相同且长度不小于5的的连续子序列的最长长度。相同定义为每个元素相同或者每个元素加上同一个数后与另一个序列相同。

输入输出格式

输入格式：
输入文件的第一行包含整数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

题解

用dp[i][j]表示以$a_i, a_j$开头的两段子序列的最长长度-1。为了方便，这里-1的意义是没有计算开头元素，即$a_i, a_j$对长度的贡献，若$a_i-a_{i-1}$与$a_j-a_{j-1}$相等，则可以从$dp[i-1][j-1]$向此处转移。显然我们应该在所有合法的DP状态中取最大值，答案就是最大值+1，不过要判断一下是否合法。
复杂度$O(n^2)$。

代码

// Code by KSkun, 2018/7
#include <cstdio>
#include <cctype>
#include <cstring>

#include <algorithm>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
        ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1; register char c = fgc();
    for(; !isdigit(c); c = fgc()) if(c == '-') neg = -1;
    for(; isdigit(c); c = fgc()) res = (res << 1) + (res << 3) + c - '0';
    return res * neg;
}

const int MAXN = 5005;

int n, a[MAXN], dp[MAXN][MAXN];

int main() {
    n = readint();
    for(int i = 1; i <= n; i++) {
        a[i] = readint();
    }
    int ans = 0;
    for(int i = 1; i <= n - 5; i++) {
        for(int j = i + 5; j <= n; j++) {
            if(a[i] - a[i - 1] == a[j] - a[j - 1]) {
                dp[i][j] = std::min(j - i - 1, dp[i - 1][j - 1] + 1);
            }
            ans = std::max(ans, dp[i][j]);
        }
    }
    printf("%d\n", ans >= 4 ? ans + 1 : 0);
    return 0;
}