usaco_5_1_3_theme.cpp

usaco自己做的1到5章的代码

/*
PROB: theme
LANG: C++
*/
/*
枚举题，它的枚举策略就很重要……
这道题，我先把这个序列相邻两个的差值算出来，然后再直接找差值中相同的，那么就不用再找那个升调了！
这道题，刚开始我3重循环的最外层是长度，然后从最长的往下搜，搜到就直接输出，结果第9组就卡住了。
后来想想，这样的话可能长度只有26，但是我却从2500搜，效率太低，所以就换成从短的往长的搜，直到第一次没搜出来就输出，这样倒是过到第11组了，但是还是超时。
然后想到，开始搜了那么多长度短于搜出来的最大值的，那么我把长度放到第二层枚举，最外层只枚举开始的位置，这样长度每次搜出来后对用最大值更新，每次从以前搜出来的最大值+1
这样，那次搜不出来了，直接跳出就好了。
经过这几遍的改进，终于A掉了！
*/
#include<iostream>
#include<fstream>
#include<memory>
#include<algorithm>
#define cin fin
#define MAXP 5005
using namespace std;

short a[MAXP];
short minu[MAXP];
int n,len,maxn;
int main()
{
    int i,j,k,des;
    ifstream fin("theme.in");
    ofstream fout("theme.out");
    cin>>n;
    len=3;maxn=-1;
    bool found,changed;
    for(i=0;i<n;i++) cin>>a[i];
    for(i=n-1;i>0;i--) minu[i-1]=a[i]-a[i-1];
    for(j=0;j<n-1;j++){
        for(i=len+1;i<=(n-j)/2;i++){
			found=false;
			changed=false;
            for(k=j+i+1;k<n-i;k++){
				if(k+i-1>n-2) continue;
                if(minu[j]!=minu[k]) continue;
                if(minu[j+i-1]!=minu[k+i-1]) continue;
                if(minu[(i+2*j)/2]!=minu[(i+2*k)/2]) continue;
                found=true;
                for(int p=0;p<i;p++)
                    if(minu[j+p]!=minu[k+p]) {found=false; break;}
				if(found) 
				{
					len=i; 
					if(len>maxn) {maxn=len; changed=true;} 
					break;
				}
		    }
			if(!found) break;
		}
    }
    fout<<maxn+1<<endl;
    return 0;
}