usaco training 5.1.3 Musical Themes 문제 풀이

[원제]
Musical Themes 문제 해결 Brian Dean
A musical melody is represented as a sequence of N (1 <= N <= 5000) notes that are integers in the range 1..88, each representing a key on the piano. It is unfortunate but true that this representation of melodies ignores the notion of musical timing; but, this programming task is about notes and not timings.
Many composers structure their music around a repeating "theme", which, being a subsequence of an entire melody, is a sequence of integers in our representation. A subsequence of a melody is a theme if it:

is at least five notes long

appears (potentially transposed -- see below) again somewhere else in the piece of music

is disjoint from (i.e., non-overlapping with) at least one of its other appearance(s)

Transposed means that a constant positive or negative value is added to every note value in the theme subsequence.
Given a melody, compute the length (number of notes) of the longest theme.
One second time limit for this problem's solutions!

PROGRAM NAME: theme

INPUT FORMAT

The first line of the input file contains the integer N. Each subsequent line (except potentially the last) contains 20 integers representing the sequence of notes. The last line contains the remainder of the notes, potentially fewer than 20.

SAMPLE INPUT (file theme.in)

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

OUTPUT FORMAT

The output file should contain a single line with a single integer that represents the length of the longest theme. If there are no themes, output 0.

SAMPLE OUTPUT (file theme.out)

5

[The five-long theme is the last five notes of the first line and the first five notes of the second] 
[역제]

묘사

우리는 N (1 < = N < = 5000) 개의 음표의 서열로 한 곡의 악곡을 표시하는데, 각 음표는 모두 1... 이다.88 범위 내의 정수, 각 수는 피아노의 키를 나타낸다.불행하게도 이런 멜로디를 나타내는 방법은 음표의 시치를 무시했지만, 이 프로그래밍 작업은 음의 높음에 관한 것으로 시치와 무관하다.
많은 작곡가들이 반복되는 주제를 둘러싸고 악곡을 세운다.우리의 악곡 표현법에서'주제'는 전체 음부 서열의 자열로 다음과 같은 조건을 충족시켜야 한다.
⒈ 길이 최소 5 음표
⒉ 악곡에 중복되어 나타날 수 있다.
⒊ 반복적으로 나타나는 동일한 주제는 공공적인 부분이 있어서는 안 된다.
'변조'는 주제 서열에 있는 모든 음표가 같은 정수치를 더하거나 줄였다는 뜻이다.악곡 한 단락을 정하고 그 중에서 가장 긴 주제의 길이(즉 음부수)를 계산한다.
이 문제의 시한은 1초입니다!

[편집] 형식

PROGRAM NAME: theme
INPUT FORMAT
입력 파일의 첫 번째 행에는 정수 N이 포함됩니다.다음 줄마다 (마지막 줄은 제외될 수 있음) 20개의 정수를 포함하여 음부 서열을 나타낸다.마지막 줄은 20개의 음표보다 적을 수 있다.
OUTPUT FORMAT
출력 파일은 가장 긴 테마의 길이인 정수만 포함해야 합니다.악곡에 주제가 없으면 0을 출력합니다.

[편집] SAMPLE INPUT(file theme.in)

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

[편집] SAMPLE OUTPUT(file theme.out)

5

(이 길이가 5인 테마는 입력 파일의 첫 번째 줄의 마지막 다섯 음표와 두 번째 줄의 시작 다섯 음표)
[분석] 너무 강해!원래는 이분일거로 검증을 하려고 했지만 검증에 대해 n^3의 폭력적 판단을 생각해낼 수 밖에 없어서 통과할 수 없었다.NOCWO의 문제풀이를 열자 가장 긴 공용 문자열에 관한 DP 방법이 내 눈에 들어왔다.이 방법은 괜찮다!
【코드1】

#include<stdio.h>
#include<iostream>
using namespace std;
int a[5005],f[5005][5005],i,j,n,ans;
int main()
{
  freopen("theme.in","r",stdin);
  freopen("theme.out","w",stdout);
  scanf("%ld",&n);
  for (i=1;i<=n;i++)
    scanf("%ld",&a[i]);
  for (i=1;i<=n;i++)
    for (j=i;j<=n;j++) 
    {
      if (a[i]-a[i-1]==a[j]-a[j-1]) 
        f[i][j]=max(f[i][j],f[i-1][j-1]+1);
      if (f[i][j]>ans) 
        ans=f[i][j];
    }
  if (ans<4) ans=-1;printf("%ld",ans+1);
  return 0;
}

[주석] 비교할 때 약간 교묘하다. 왜냐하면 음조는 변화할 수 있기 때문에 차법으로 사용하면 이 문제를 피할 수 있다.심부름을 했기 때문에 결과는 1을 더해야 한다.그러나 곧 나는 이 프로그램의 빈틈을 발견했다. 주제의 음조는 중첩될 수 없다.
[심도 있는 분석] 중복을 피하는 것도 간단하다. 바로 f[i-1][j-1][코드 2(AC)]

/*
PROG:theme
ID:juan1973
LANG:C++
*/
#include<stdio.h>
#include<iostream>
#include<cstring>
using namespace std;
int a[5005],f[2][5005],i,j,n,ans,now;
int main()
{
  freopen("theme.in","r",stdin);
  freopen("theme.out","w",stdout);
  scanf("%ld",&n);
  for (i=1;i<=n;i++)
    scanf("%ld",&a[i]);
  for (i=1;i<=n;i++)
  {
	now=i%2;
	memset(f[now],0,sizeof(f[now]));
	for (j=i;j<=n;j++) 
    {
	  if (a[i]-a[i-1]==a[j]-a[j-1]&&f[now^1][j-1]<j-i-1) 
        f[now][j]=max(f[now][j],f[now^1][j-1]+1);
      if (f[now][j]>ans) 
        ans=f[now][j];
    }
  }
  if (ans<4) ans=-1;printf("%ld",ans+1);
  return 0;
}