题意

给出一个序列\(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\n", 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;

}