【链接】 我是链接,点我呀:)
【题意】
在这里输入题意
【题解】
枚举序列的头两个数字是什么
O(N^2)
然后头两个数字确定之后。
f[3],f[4]..就确定了
只需查看f[3],f[4]..是不是存在就好了。
但是这样复杂度看起来是O(N^3)的了。
其实不然,a[n] = a[n-1]+a[n-2]这个递推的增长速度是接近2^n的增长速度的。
(所以到达10^9之后直接break就好了
所以实际上不会真的达到递推1000的规模
差不多只有O(N^2*100)的样子。
这是可以接受的了。
->但是有一种情况要特判,就是f[1] = f[2]=0的情况。这种情况直接统计1的个数即可。
程序中还加了一个优化。
因为前两项f1,f2确定之后f[i] = xf1+yf2
则我们提前算出来系数。
就能直接得到前两项是f1,f2的前提下fi的值了
根据这个可以做一下剪枝。
【代码】
#include <bits/stdc++.h>
using namespace std;
const int N = 1000;
int a[N+10],n,b[N+10];
map<int,int> dic;
int x[N+10],y[N+10];
int main(){
#ifdef LOCAL_DEFINE
freopen("rush_in.txt", "r", stdin);
#endif
ios::sync_with_stdio(0),cin.tie(0);
x[1] = 1;y[1] = 0;
x[2] = 0;y[2] = 1;
x[3] = y[3]= 1;
for (int i = 4;i <=N;i++){
x[i] = x[i-2]+x[i-1];
y[i] = y[i-2]+y[i-1];
}
cin >> n;
for (int i = 1;i <= n;i++) {
cin >> a[i];
dic[a[i]]++;
}
int ans = 2;
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++)
if (i!=j){
if (a[i]==0 && a[j]==0){
int num = dic[0];
ans = max(ans,num);
continue;
}
dic[a[i]]--,dic[a[j]]--;
int num = 2;
b[1] = a[i],b[2] = a[j];
if (ans>2 && ans<=40){
long long temp = 1LL*x[ans]*a[i]+1LL*y[ans]*a[j];
if (abs(temp)>1e9|| dic[temp]==0){
dic[a[i]]++,dic[a[j]]++;
continue;
}
}
for (int k = 3;k<=n;k++){
b[k] = b[k-2]+b[k-1];
if (abs(b[k])>1e9) break;
if (dic[b[k]]>0){
dic[b[k]]--;
num++;
}else break;
}
ans =max(ans,num);
for (int k = 1;k <= num;k++) dic[b[k]]++;
}
cout << ans << endl;
return 0;
}