本文正體字版由OpenCC轉換

這個題考慮到相同的旋律之間的差是常數，可以把讀入的序列變換一下。就是每個元素與其前一個元素做差。例如原序列{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