记录编号	195723	评测结果	AAAAAAAAAAAAAAA
题目名称	乐曲主题	最终得分	100
用户昵称	mikumikumi	是否通过	通过
代码语言	C++	运行时间	0.098 s
提交时间	2015-10-19 16:53:54	内存使用	0.39 MiB

#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
using namespace std;
const int SIZEN=5010;
int N,S[SIZEN];
int height[SIZEN],rank[SIZEN],sa[SIZEN];
class miku
{
public:
	int id;
	int key1,key2;//
};//用来快排的类
void read()
{
	scanf("%d",&N);
	for(int i=1;i<=N;i++) scanf("%d",&S[i]);
	for(int i=1;i<N;i++) S[i]=S[i+1]-S[i]+90;
	N--;
}
bool cmp(miku a,miku b)
{
	if(a.key1==b.key1&&a.key2==b.key2) return a.id<b.id;
	if(a.key1==b.key1) return a.key2<b.key2;
	return a.key1<b.key1;
}
void make_sa()//倍增
{
	miku P[SIZEN];
	for(int i=1;i<=N;i++) P[i].key1=S[i],P[i].key2=0,P[i].id=i;
	sort(P+1,P+N+1,cmp);
	for(int i=1;i<=N;i++) sa[i]=P[i].id;
	rank[sa[1]]=1;
	for(int i=2;i<=N;i++) 
		if(S[sa[i-1]]==S[sa[i]]) rank[sa[i]]=rank[sa[i-1]];
			else rank[sa[i]]=rank[sa[i-1]]+1;
	for(int k=1;k<=N;k<<=1)
	{
		for(int i=1;i<=N;i++)
		{
			P[i].id=i;
			P[i].key1=rank[i];
			if(i+k<=N) P[i].key2=rank[i+k];
			else P[i].key2=0;
		}
		sort(P+1,P+N+1,cmp);
		for(int i=1;i<=N;i++) sa[i]=P[i].id;
		rank[sa[1]]=1;
		for(int i=2;i<=N;i++)
		{
			if(P[i].key1==P[i-1].key1&&P[i].key2==P[i-1].key2) rank[P[i].id]=rank[P[i-1].id];
			else rank[P[i].id]=rank[P[i-1].id]+1;
		}
	}
	for(int i=1;i<=N;i++) rank[sa[i]]=i;
}
void calc_height()
{
	int h=0;
	for(int i=1;i<=N;i++)
	{
		if(rank[i]==1) h=0;
		else
		{
			int k=sa[rank[i]-1];
			h--;
			if(h<0) h=0;
			while(S[i+h]==S[k+h]) h++;
		}
		height[rank[i]]=h;
	}
}
void prepare()
{
	make_sa();
	calc_height();
}
bool check(int k)
{
	int i=1;
	while(i<N)
	{
		int j=i+1,mx,mn;
		mn=mx=sa[i];
		while(j<=N&&height[j]>=k)
		{
			mx=max(mx,sa[j]);
			mn=min(mn,sa[j]);
			j++;
		}
		if(mx-mn>k) return 1;
		i=j;
	}
	return 0;
}
void work()
{
	int l=0,r=N/2;
	while(l<r)
	{
		int mid=(l+r)/2;
		if(check(mid+1)) l=mid+1;
		else r=mid;
	}
	if(l>=4) printf("%d\n",l+1);
	else printf("0\n");
}
int main()
{
	freopen("theme.in","r",stdin);
	freopen("theme.out","w",stdout);
	read();
	prepare();
	work();
	return 0;
}