首页 > 代码库 > bzoj 3357: [Usaco2004]等差数列

bzoj 3357: [Usaco2004]等差数列

3357: [Usaco2004]等差数列

Time Limit: 10 Sec  Memory Limit: 128 MB

Description

    约翰发现奶牛经常排成等差数列的号码.他看到五头牛排成这样的序号:“1,4,3,5,7”
很容易看出“1,3,5,7”是等差数列.
    给出N(1≤N≤2000)数字AI..AN(O≤Ai≤10^9),找出最长的等差数列,输出长度.

Input

    第1行:一个整数N.
    第2到N+1行:每行一个整数Ai,表示牛的号码.

Output

 
    最长等差数列的长度.

Sample Input

5
1
4
3
5
7

Sample Output

4

HINT

 

#include<map>
#include<cstdio>
#define M 2020
using namespace std;
int n,ans,a[M];
map<int,int>f[M];
int main()
{
    int i,j;
    scanf("%d",&n);
    for(i=1;i<=n;i++) scanf("%d",&a[i]);
    if(n==1)printf("1");
    else{
    for(i=1;i<=n;i++)
    for(j=1;j<i;j++)
    {
        f[i][a[j]]=max(f[i][a[j]],2);
        f[i][a[j]]=max(f[i][a[j]],f[j][a[j]*2-a[i]]+1);
        ans=max(ans,f[i][a[j]]);
    }
    printf("%d",ans);}
}

 

bzoj 3357: [Usaco2004]等差数列