51Nod 1055 最长等差数列 (dp+哈希)

1055 最长等差数列 51Nod 1055 最长等差数列 (dp+哈希)-LMLPHP

基准时间限制：2 秒空间限制：262144 KB 分值: 80 难度：5级算法题

N个不同的正整数，找出由这些数组成的最长的等差数列。

例如：1 3 5 6 8 9 10 12 13 14

等差子数列包括(仅包括两项的不列举）

1 3 5

1 5 9 13

3 6 9 12

3 8 13

5 9 13

6 8 10 12 14

其中6 8 10 12 14最长，长度为5。

Input

第1行：N，N为正整数的数量(3 <= N <= 10000)。

第2 - N+1行：N个正整数。(2<= A[i] <= 10^9)

Output

最长等差数列的长度。

Input示例

Output示例



#include<bits/stdc++.h>

#include<stdio.h>

#include<iostream>

#include<cmath>

#include<math.h>

#include<queue>

#include<set>

#include<map>

#include<iomanip>

#include<algorithm>

#include<stack>

#include<hash_map>

using namespace std;

#define inf 0x3f3f3f3f

typedef long long ll;

const int maxn  = 10002;

short dp[10002][10002];

int a[10002];

int n;

const int BUCKET_SIZE   = 42839;

const int NEXT_POS      = 7;

typedef struct _my_hash

{

    int _bucket[BUCKET_SIZE];

    int _key[BUCKET_SIZE];

    _my_hash()

    {

        memset(_bucket, 0, sizeof(_bucket[0]) * BUCKET_SIZE);

        memset(_key, 0, sizeof(_key[0]) * BUCKET_SIZE);

    }

    void insert(int key, int value)

    {

        int mod = key % BUCKET_SIZE;

        while (_key[mod] != 0)

        {

            mod = (mod + NEXT_POS) % BUCKET_SIZE;

        }

        _bucket[mod]    = value;

        _key[mod]       = key;

    }

    int find(int key)

    {

        int origin = key % BUCKET_SIZE;

        int mod = key % BUCKET_SIZE;

        while (_key[mod] != 0)

        {

            if (_key[mod] == key)

            {

                return _bucket[mod];

            }

            mod = (mod + NEXT_POS) % BUCKET_SIZE;

            if (mod == origin)

            {

                return -1;

            }

        }

        return -1;

    }

}my_hash_t;

my_hash_t h;

short d(int j,int k) {

    if(dp[j][k]>=0) return dp[j][k];

    dp[j][k]=2;

    int ai=a[j]-(a[k]-a[j]);

    int i=h.find(ai);

    if(i<1) return dp[j][k];

    dp[j][k]=d(i,j)+1;

    return dp[j][k];

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("in.txt","r",stdin);

#endif // ONLIN

    scanf("%d",&n);

    for(int i=1;i<=n;i++) {

        scanf("%d",&a[i]);

    }

    sort(a+1,a+n+1);

    for(int i=1;i<=n;i++) h.insert(a[i],i);

    short ans=-1;

    for(int j=1;j<n;j++) {

        for(int k=j+1;k<=n;k++) {

            int i=h.find(2*a[j]-a[k]);

            if(i<0) continue;

            dp[j][k]=dp[i][j]+1;

            ans = max(ans,dp[j][k]);

        }

    }

    cout<<ans+2<<endl;

}