这个题考虑到相同的旋律之间的差是常数，可以把读入的序列变换一下。就是每个元素与其前一个元素做差。例如原序列{3,5,7,3,4,4,6,8,4}，做差后是{2,2,-4,1,0,2,2,-4}。这样就可以再变换后的序列中直接查找最长的重复序列即可。上述例子中是2,2,-4，长度为3，对应原序列中3,5,7,3，长度为4。

寻找最长的重复序列，我采用了一种O(N^3)的算法。就是枚举两个序列的开头的序列的长度。但对于5000，O(N^3)还是难以过全的。于是采用了一个优化：每次枚举末端那一位时都从开始的一位加上当前最大长度开始枚举，前一个序列开头只用枚举到(N-当前的最大长度)即可。这个优化的力度很大，加上这个优化就全过了，而且很快。

提醒一下，Pascal的For循环 for i=1 to n-ans，当ans再循环中改变时，循环次数不会随之变化，也就是说一开始循环的次数就算好了。而C和C++中 for(i=1;i<=n-ans;i++)会每次计算n-ans，所以ans改变时循环的次数也会改变。

USER: CmYkRgB123 CmYkRgB123 [cmykrgb1]
TASK: theme
LANG: C++

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.011 secs, 2864 KB]
   Test 2: TEST OK [0.011 secs, 2860 KB]
   Test 3: TEST OK [0.011 secs, 2860 KB]
   Test 4: TEST OK [0.000 secs, 2864 KB]
   Test 5: TEST OK [0.000 secs, 2864 KB]
   Test 6: TEST OK [0.000 secs, 2860 KB]
   Test 7: TEST OK [0.011 secs, 2860 KB]
   Test 8: TEST OK [0.011 secs, 2864 KB]
   Test 9: TEST OK [0.000 secs, 2864 KB]
   Test 10: TEST OK [0.022 secs, 2864 KB]
   Test 11: TEST OK [0.097 secs, 2860 KB]
   Test 12: TEST OK [0.076 secs, 2860 KB]
   Test 13: TEST OK [0.011 secs, 2860 KB]
   Test 14: TEST OK [0.216 secs, 2864 KB]
   Test 15: TEST OK [0.000 secs, 2860 KB]

All tests OK.

Your program ('theme') produced all correct answers!  This is your
submission #2 for this problem.  Congratulations!

/*
ID: cmykrgb1
PROG: theme
LANG: C++
*/

#include <iostream>
#include <fstream>
#define MAXN 5001
#define INF 0x7FFFFFFF

using namespace std;

ifstream fi("theme.in");
ofstream fo("theme.out");

int N,ans;
int a[MAXN];

void init()
{
	int i,p,q;
	fi >> N >> p;
	for (i=1;i<=N;i++)
	{
		fi >> q;
		a[i]=q-p;
		p=q;
	}
	a[N]=INF;
}

void compute()
{
	int i,j,len,k;
	for (i=1;i<=N-ans;i++)
		for (j=i+ans;j<=N-ans;j++)
			if (a[i]==a[j])
			{
				len=1;
				k=j;
				while (a[i+len]==a[j+len] && k>i+len+1) len++;
				if (len>ans)
					ans=len;
			}
}

void print()
{
	if (ans<4)	ans=-1;
	fo << ans+1 << endl;
	fi.close();
	fo.close();
}

int main()
{
	init();
	compute();
	print();
	return 0;
}

上次修改时间 2017-05-22