【CodeForces - 633D】Fibonacci-ish （离散化，暴力枚举+STPmap，fib数列收敛性质）

题干：

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

f0 and f1 are arbitrary

fn + 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

3 1 2 -1

Output

3

Input

5 28 35 7 14 21

Output

4

Note

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.

题目大意：

     定义，fib数列：f[0]、f[1]任意，对于n > 1，f[n] = f[n-1] + f[n-2]。给定n个元素，构造最长的fib数列，输出长度。

解题报告：

     由于斐波那契数列数值成指数型增长(称为斐波那契数列的收敛性)，所以实际可选的长度不会超过100(实际上增长速度仅仅比2的幂次方要慢一点点。若是正整数的斐波那契数列，要从0 1增长到1e9只需40位左右，所以题中样例给出的长度最大也是接近90的)。那么只需离散出全部的不同的数值及其个数，枚举前两位即可。有个特例，如果前两位为0，这时可以造一个样例长度可能达到1000，但只会出现一次。。。所以无伤大雅。（好像cf里没有这个样例）

    时间复杂度o(100 * n^2logn)左右。

TLE3代码：

#include<bits/stdc++.h> #define ll long long using namespace std; ll a[2005]; int n; ll max(ll x,ll y) {if(x > y) return x;return y; } ll solve(int p1,int p2) {ll res = 2,tmp = 0;int pos = 1;ll r[3] = {a[p1],a[p2]};while(1) {if(binary_search(a+1,a+n+1,r[0] + r[1]) == 0) break;res++;r[2] = r[0]+r[1];r[0]=r[1]; r[1]=r[2];} return res; } int main() {ll maxx = 0;cin>>n;for(int i = 1; i<=n; i++) scanf("%lld",a+i);sort(a+1,a+n+1);for(int i = 1; i<=n; i++) {for(int j = 1; j<=n; j++) {if(j == i) continue;maxx = max(maxx,solve(i,j));}}printf("%lld\n",maxx);return 0 ;}

究其原因，，貌似是因为没有离散化？但是貌似离散化也离散不了哪里去吧，也就是可以下标存下这个元素了，但是查找的时候还是log的复杂度啊。。

 

AC代码：（700ms左右）

离散化后用map存出现次数，但是其实因为都离散化了，就不需要map了啊（因为下标已经是<1000的了），所以直接二分找位置然后开num数组存离散化后值出现的次数就好了呀。

#include<bits/stdc++.h> #define ll long long using namespace std; ll a[2005]; int n,len; map<ll,ll> mp; ll max(ll x,ll y) {if(x > y) return x;return y; } ll solve(int p1,int p2) {ll res = 2,tmp = 0;int pos = 1;ll r[3] = {a[p1],a[p2]};mp[r[0]]--;mp[r[1]]--;while(1) {if(mp[r[0]+r[1]] == 0) break;res++;r[2] = r[0]+r[1];r[0]=r[1]; r[1]=r[2];mp[r[1]]--;//mp[r[0]]--;} mp[r[1]]++;mp[r[0]]++;while(1) {if(r[0] == a[p1] && r[1] == a[p2]) break;r[2] = r[1]-r[0];r[1] = r[0];r[0] = r[2];mp[r[0]]++;}return res; }int main() {ll maxx = 0;cin>>n;for(int i = 1; i<=n; i++) scanf("%lld",a+i),mp[a[i]]++;sort(a+1,a+n+1);len = unique(a+1,a+n+1) - a - 1;for(int i = 1; i<=len; i++) {for(int j = 1; j<=len; j++) {if(j == i && mp[a[i]] <= 1) continue;maxx = max(maxx,solve(i,j));}}printf("%lld\n",maxx);return 0 ;}

另：这题solve函数中完全没有必要两边while，其实一遍就可以，顺便记录下用到了哪些值，最后直接遍历这些值然后num[]++不就好了。

AC代码2：（网上大部分都是给的递归的形式，但是有什么卵用呢、、）

#include<bits/stdc++.h> #define ll long long using namespace std; ll a[2005]; int n,len; map<ll,ll> mp; ll max(ll x,ll y) {if(x > y) return x;return y; } int f(ll a,ll b) {ll ans=0;if(mp[a+b]) {mp[a+b]--;ans=f(b,a+b)+1;mp[a+b]++;}return ans; }int main() {ll maxx = 0;cin>>n;for(int i = 1; i<=n; i++) scanf("%lld",a+i),mp[a[i]]++;sort(a+1,a+n+1);len = unique(a+1,a+n+1) - a - 1;for(int i = 1; i<=len; i++) {for(int j = 1; j<=len; j++) {if(j == i && mp[a[i]] <= 1) continue;mp[a[i]]--;mp[a[j]]--;maxx = max(maxx,f(a[i],a[j]));mp[a[i]]++;mp[a[j]]++;}}printf("%lld\n",maxx+2);return 0 ;}

 

附一个网络AC代码没用map的：

#include<iostream> #include<cstdio> #include<cstring> #include<string.h> #include<algorithm> #include<vector> #include<cmath> #include<stdlib.h> #include<time.h> #include<stack> #include<set> #include<map> #include<queue> using namespace std; #define rep0(i,l,r) for(int i = (l);i < (r);i++) #define rep1(i,l,r) for(int i = (l);i <= (r);i++) #define rep_0(i,r,l) for(int i = (r);i > (l);i--) #define rep_1(i,r,l) for(int i = (r);i >= (l);i--) #define MS0(a) memset(a,0,sizeof(a)) #define MS1(a) memset(a,-1,sizeof(a)) #define MSi(a) memset(a,0x3f,sizeof(a)) #define inf 0x3f3f3f3f #define lson l, m, rt << 1 #define rson m+1, r, rt << 1|1 typedef __int64 ll; void out(T a) {if(a>9) out(a/10);putchar(a%10+'0'); } int v[1010],num[1010],stk[1010];//stk长度也要为1000，因为前面两个为0时,len可能为最大值 int main() {int n;read1(n);rep0(i,0,n) read1(v[i]);sort(v,v + n);int ans = 0,cnt = 0;rep0(i,0,n){int t = i;while(i < n - 1 && v[i] == v[i + 1]) i++;num[cnt] = i - t + 1;v[cnt++] = v[i];//压缩}v[cnt] = 2e9;rep0(i,0,cnt){rep0(j,0,cnt){if(i != j || num[j] > 1){stk[1] = i;stk[2] = j;int len = 2,val = v[i] + v[j];num[i]--,num[j]--;int down = lower_bound(v,v+cnt,val) - v;while(v[down] == val && num[down]){num[down]--;val -= v[stk[len-1]];val += v[down];stk[++len] = down;down = lower_bound(v,v+cnt,val) - v;}ans = max(ans,len);rep1(i,1,len) num[stk[i]]++;}}}out(ans);return 0; }

 

创作挑战赛新人创作奖励来咯，坚持创作打卡瓜分现金大奖

总结

以上是生活随笔为你收集整理的【CodeForces - 633D】Fibonacci-ish （离散化，暴力枚举+STPmap，fib数列收敛性质）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。