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 elementsf0 and f1 are arbitraryfn + 2 = fn + 1 + fn for all n ≥ 0.You are given some sequence of integers a1, a2, ..., an. 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 ai.
The second line contains n integers a1, a2, ..., an (|ai| ≤ 109).
Output
Print the length of the longest possible Fibonacci-ish prefix of the given sequence after rearrangement.
Examples
Input 31 2 -1 Output 3 Input 528 35 7 14 21 Output 4Note
In the first sample, if we rearrange elements of the sequence as - 1, 2, 1, the whole sequence ai 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]>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
