#P1987. Zju2672 Fibonacci Subsequence

Zju2672 Fibonacci Subsequence

题目描述

给定长度为 NN 的整数序列 AA,求最长的满足如下条件的子序列 BB:

  • ∀i∈[3,k],Bi=Bi−1+Bi−2\forall i\in [3,k], B_i = B_{i-1} + B_{i-2},其中 kk 是 BB 的长度。

你需要最大化 kk,然后构造方案。

输入格式

第一行一个整数 NN。第二行 NN 个整数 A1,…,ANA_1,…,A_N。

输出格式

若最长长度不足 33,只输出一行 00。否则第一行输出最长长度 kk,第二行输出该子序列的 kk 个值。若有多个最优解,选择原序列下标序列字典序最小的一组。

样例

6 
10 1 2 20 30 3

3 
10 20 30 

数据范围

1≤N≤30001\le N\le3000,∣Ai∣≤109|A_i|\le10^9。

原赛题面 PDF