【-89】P2743 [USACO5.1]乐曲主题Musical Themes[dp]

题目描述

我们用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

题解

一道比较简单的dp题
f[i][j]表示以 第一个部分以第i个字符为结尾,第二个部分以第j个字符为结尾,主题的长度。
dp转移方程f[i][j]=f[i-1][j-1]+1(a[i]-a[i-1]==a[j]-a[j-1])
f[i][j]=1(a[i]-a[i-1]!=a[j]-a[j-1])
然而不能有重叠部分,我们可以发现,f[i][j]最大为j-i,所以要加个限制f[i-1][j-1]+1<=j-i
然后开5k*5k的数组会炸(在usaco上),所以用滚动数组(多棒)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/*
ID: ylx14271
PROG: theme
LANG: C++
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
int a[5010];
int i,j,k,n;
int f[2][5010];
int ans;
int main()
{
freopen("theme.in","r",stdin);
freopen("theme.out","w",stdout);
scanf("%d",&n);
for (i=1;i<=n;i++) scanf("%d",&a[i]);//读入
for (i=1;i<n-4;i++)//因为长度最大为5,所以只搞到n-4
for (j=i+1;j<=n;j++)//不能重叠,所以i+1开始
{
if (a[i]-a[i-1]==a[j]-a[j-1]&&f[(i-1)%2][j-1]+1<=j-i)//判重
f[i%2][j]=f[(i-1)%2][j-1]+1; else f[i%2][j]=1;
ans=max(ans,f[i%2][j]);
}
if (ans<5) ans=0;
printf("%d\n",ans);//输出
return 0;
}