题干：
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;
}
京公网安备 11010502036488号