CodeForces - 633D Fibonacci-ish 大数标记map+pair的使用

Fibonacci-ish

Yash has recently learnt about the Fibonacci sequence and is very excited about it. He calls a sequence Fibonacci-ish if

the sequence consists of at least two elements
f₀ and f₁ are arbitrary
f_n + 2 = f_n + 1 + f_n for all n ≥ 0.

You are given some sequence of integers a₁, a₂, ..., a_n. Your task is rearrange elements of this sequence in such a way that its longest possible prefix is Fibonacci-ish sequence.

Input

The first line of the input contains a single integer n (2 ≤ n ≤ 1000) — the length of the sequence a_i.

The second line contains n integers a₁, a₂, ..., a_n (|a_i| ≤ 10⁹).

Output

Print the length of the longest possible Fibonacci-ish prefix of the given sequence after rearrangement.

Examples

Input

3
1 2 -1

Output

Input

5
28 35 7 14 21

Output

Note

In the first sample, if we rearrange elements of the sequence as - 1, 2, 1, the whole sequence a_i would be Fibonacci-ish.

In the second sample, the optimal way to rearrange elements is , , , , 28.

从已知元素中寻找最长斐波那契长度。

个人非常喜欢的一道题，比较综合。用到了一些套路，比如用map标记大数，以及加上pair来标记一组数。

开始有往dp方向考虑，想先给数列排个序，然后依次往右找。但是两数相加不一定会变大，和可能会在左边，比如本题负数情况。

再一个每次寻找下一个值时，都要重新使用标记，为了防止后效性，使用递归来处理。

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<math.h>

#include<set>

#include<map>

#include<algorithm>

#define MAX 1005

#define INF 0x3f3f3f3f

using namespace std;

int a[MAX],c;

map<int,int> mp;

map<pair<int,int>,int> mmp;

void dfs(int x,int y){     //递归寻找

    if(mp[x+y]>) {

        c++;

        mp[x+y]--;

        dfs(y,x+y);

        mp[x+y]++;

    }

}

int main()

{

    int n,i,j;

    scanf("%d",&n);

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

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

        mp[a[i]]++;      //大数标记

    }

    int max=;

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

        for(j=;j<=n;j++){    //考虑负数情况

            if(i!=j){

                if(mmp[make_pair(a[i],a[j])]) continue;

                mmp[make_pair(a[i],a[j])]=;     //标记一对数，优化防T

                c=;

                mp[a[i]]--;

                mp[a[j]]--;

                dfs(a[i],a[j]);

                mp[a[i]]++;

                mp[a[j]]++;

                if(c>max) max=c;

            }

        }

    }

    printf("%d\n",max);

    return ;

}

巴特西

CodeForces - 633D Fibonacci-ish 大数标记map+pair的使用

Fibonacci-ish

最新文章

热门文章