到处乱逛找到的一道有意思的题。
定义斐波那契序列为：前两项值不做限制，\(f_i=f_{i-1}+f_{i-2}(2<i\le n)\)。
给定一个长度为 \(n\) 的序列 \(a\)，找出其最长的斐波那契子序列。
如果有多个最长输出字典序最小的一个。
正解做法貌似为 \(n^2logn\)。即动态规划加二分。
但我用一些优化trick加一个貌似是 \(n^3logn\) 的做法搞过了。
首先用一个 \(unordered\_map\) 对原序列进行离散化。
可以发现一个斐波那契序列可以由前两位唯一标识。字典序也只与前两位相关。
然后开 \(n\) 个桶来存放对应数字的下标。
每次在数组里选两个数，根据这两个数来推长度。每次只需要在桶里二分找到一个最小的可以加入斐波那契序列的下标然后加入。
然后再加上一个优化就是在选数过程中如果选到的数的下标已经劣于当前找到的最长序列长度，那就不用往下推了。
然后就做完了。貌似随机数据下跑的比正解还快？
view
#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define fir first
#define sec second
#define re register
#define ios ios::sync_with_stdio(0),cin.tie(0)
#define il inline
using namespace std;
int n,a[3001],tot,num[3001];
bool vis[3001][3001];
ll MX,MI=2e9;
vector<int>g[3001];
unordered_map<int,int>mp;
int s1,s2,mx;
il void calc(int i,int j){re int l=i,r=j,len=2,x=a[l],y=a[r];vis[l][r]=1;while(1){re ll k=x*1ll+y*1ll;if(k>MX||k<MI)break;int id=mp[k];auto it=upper_bound(g[id].begin(),g[id].end(),r);if(it==g[id].end())break;int p=*it;if(p>r)x=a[r],y=a[p],vis[r][p]=1,r=p;else break;len++;}if(len>mx)mx=len,s1=a[i],s2=a[j];else if(len==mx){if(a[i]<s1)s1=a[i],s2=a[j];else if(a[i]==s1&&a[j]<s2)s1=a[i],s2=a[j];}
}
signed main(){ios;cin>>n;for(re int i=1;i<=n;i++){cin>>a[i],MX=max(MX,a[i]*1ll),MI=min(MI,a[i]*1ll);if(!mp[a[i]])mp[a[i]]=(++tot),num[tot]=a[i];g[mp[a[i]]].emplace_back(i);}for(re int i=1;i<=n;i++)for(re int j=i+1;j<=n-mx;j++)if(!vis[i][j])calc(i,j);cout<<mx<<'\n',mx-=2;cout<<s1<<' '<<s2<<' ';while(mx--){re int f=s1+s2;cout<<f<<' ',s1=s2,s2=f;}
}
)
