Codeforces--633D--Fibonacci-ish （map+去重）（twice）-白红宇

Codeforces--633D--Fibonacci-ish （map+去重）（twice）

阅读量：5140 次

发布时间：2019-06-13

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

Time Limit: 3000MS

Memory Limit: 524288KB

64bit IO Format: %I64d & %I64u

Description

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.

Sample Input

Input

31 2 -1

Output

Input

528 35 7 14 21

Output

Sample Output

Hint

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.

Source

我去，以前做过的，就记得是dfs，但是忘记要用map跟去重了，真是人老了，记性不行咯

#include
     
      #include
      #include
       
        #include
        
         using namespace std;int num[1010];map
         
          fp;int DFS(int a, int b){	int ans = 0;	if (fp[a + b])	{		fp[a + b]--;		ans=DFS(b, a + b)+1;		fp[a + b]++;	}	return ans;}int main(){	int n;	while (cin >> n)	{		memset(num, 0, sizeof(num));		fp.clear();		for (int i = 0; i < n; i++)			cin >> num[i], fp[num[i]]++;		sort(num, num + n);		int ans = 0;		int N = unique(num, num + n)-num;		for (int i = 0; i < N; i++)		{			for (int j = 0; j < N; j++)			{				if (i == j&&fp[num[i]] == 1) continue;				fp[num[i]]--, fp[num[j]]--;				ans = max(ans, DFS(num[i], num[j]) + 2);				fp[num[i]]++, fp[num[j]]++;			}		}		cout << ans << endl;	}	return 0;}