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

/*
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 小阮 阅读(271) 评论(0)  编辑 收藏 引用 所属分类: USACO

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


Powered by: 博客园 模板提供：沪江博客 Copyright ©2024 小阮