随笔-141  评论-9  文章-3  trackbacks-0
将相邻的数做差之后,转换为求最长重复子序列。

/*
ID: lorelei
TASK: theme
LANG: C++
*/


#include 
<fstream>

using namespace std;

const int MAXN = 5005;
const int INF = 0x7FFFFFFF;

ifstream fin(
"theme.in");
ofstream fout(
"theme.out");

int a[MAXN];
int n, ans;

void input(){
    
int p,q;
    fin
>>n>>p;
    
for(int i=1; i<n; ++i){
        fin
>>q;
        a[i]
=q-p;
        p
=q;
    }

}


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

}


void output(){

    
if(ans<4) ans = -1;
    fout
<<ans+1<<endl;
}


int main(){

    input();

    solve();

    output();

    
return 0;
}

posted on 2011-02-08 19:09 小阮 阅读(277) 评论(0)  编辑 收藏 引用 所属分类: USACO

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理