题意
给出一个序列(A)，求一个最长的满足fib性质的子序列，输出其长度及其元素（如果多种方案，输出位置最靠前的）。（(n le 3000)）
题解
容易想到dp，即(d(i, j))表示(i)作为fib序列的倒数第二项且(j)作为fib序列的最后一项的最大长度。
那么很容易通过(a[i]-a[j])得到转移。
然后发现倒推很好求出位置序列字典序最小的方案。
方案的话..有了长度有了前两项，你还不会求？
坑点：
bzoj上题意不对，应该是输出位置最靠前的方案，即位置序列的字典序最小。
开hash和开map就mle系列...还是老老实实二分...
#include <bits/stdc++.h>
#include <hash_map>
using namespace std;
const int N=3005;
int a[N], n, d[N][N], ans, b[N], pos[N], cnt;
int main() {
scanf("%d", &n);
for(int i=1; i<=n; ++i) scanf("%d", &a[i]), b[i]=a[i];
sort(b+1, b+1+n);
cnt=unique(b+1, b+1+n)-b-1;
for(int j=n; j>=2; --j) {
for(int i=1; i<j; ++i) {
int k=0, ps=lower_bound(b+1, b+1+cnt, a[i]+a[j])-b;
if(b[ps]==a[i]+a[j]) k=pos[ps];
if(k) d[i][j]=d[j][k]+1;
else d[i][j]=2;
ans=max(ans, d[i][j]);
}
pos[lower_bound(b+1, b+1+cnt, a[j])-b]=j;
}
if(ans<3) { puts("0"); return 0; }
printf("%d
", ans);
for(int i=1; i<n; ++i) for(int j=i+1; j<=n; ++j) if(d[i][j]==ans) {
printf("%d", a[i]);
int x=a[i], y=a[j], t;
for(int i=2; i<=ans; ++i) {
printf(" %d", y);
t=y;
y=x+y;
x=t;
}
return 0;
}
return 0;
}