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

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

阅读量：4950 次

发布时间：2019-06-11

本文共 1925 字，大约阅读时间需要 6 分钟。

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 $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , $\text{[math]}$ , 28.

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

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

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

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

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #define MAX 1005#define INF 0x3f3f3f3fusing namespace std;int a[MAX],c;map
            
              mp;map
             
              
               ,int> mmp;void dfs(int x,int y){ //递归寻找 if(mp[x+y]>0) { c++; mp[x+y]--; dfs(y,x+y); mp[x+y]++; }}int main(){ int n,i,j; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&a[i]); mp[a[i]]++; //大数标记 } int max=0; for(i=1;i<=n;i++){ for(j=1;j<=n;j++){ //考虑负数情况 if(i!=j){ if(mmp[make_pair(a[i],a[j])]) continue; mmp[make_pair(a[i],a[j])]=1; //标记一对数，优化防T c=2; 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 0;}

转载于:https://www.cnblogs.com/yzm10/p/8724574.html

你可能感兴趣的文章