| Comments

ZOJ2672

Fibonacci Subsequence

Description A sequence of integer numbers a1 , a2 , …, an is called a Fibonacci sequence if ai = ai-2+ai-1 for all i=3,4,…,n.

Given a sequence of integer numbers c1 , c2 , …, cm you have to find its longest Fibonacci subsequence.

Input

There are several test cases in the input. The first line of each case contains m ( 1 <= m <= 3,000). Next line contains m integer numbers not exceeding 109 by their absolute value. There is a new line between each case.

Output

On the first line of each case print the maximal length of the Fibonacci subsequence of the given sequence. On the second line print the subsequence itself. There is a new line between each case. Example

Input

10

1 1 3 -1 2 0 5 -1 -1 8

Output

5

1 -1 0 -1 -1

题目要求找出最长的斐波那契数列。不禁让我想起了之前的最长上升序列 摆明了要dp。题目卡了内存，比较恶心， 因此要用 short int.

dp[i][j] = max(dp[m][i]+1) i ,j 表示以第i个数和第j个数为结尾最长的序列 ，m 则是满足斐波那契条件的前i-1个数中的编号

找到m可以用2分查找优化 ， 最简单的还是放到 map里面去 用find 找 ，据说直接用[] 会超时。

最后就是 因为 斐波那契数列只要有两个数就能决定 整个序列 ，所以只要找到最大的两个数就行了，其他可以顺推出来， 这样就不用把路径记录下来了

然后是代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

#include<cstdio>
#include<iostream>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<map>
#include<stack>
typedef  long long LL;

#define clr(x) memset((x),0,sizeof(x))
#define inf 0x3f3f3f3f
using namespace std;
short int dp[3100][3100];
int n;
int a[3100];
map <int ,int > mp;


int main()
{
    while(~scanf("%d",&n))
    {
        mp.clear();
        memset(dp,0,sizeof dp);
        for(int i =0;i<n;i++)
            scanf("%d",&a[i]);
        if(n ==1)
        {
            printf("1\n%d\n",a[0]);
            continue;
        }
        mp[a[0]] = 0;
        for(int i =1;i<n;i++)
            dp[0][i] = 2;
        for(int i = 1;i<n;i++)
        {
            for(int j = i+1;j<n;j++)
            {
                int k = a[j] - a[i];
                if(mp.find(k)!=mp.end())
                {
                    dp[i][j] = max(dp[i][j],(short)(dp[mp[k]][i]+(short)1));
                }else {
                    dp[i][j] =max(dp[i][j],(short int )2);
                }

            }
            mp[a[i]] = i;
        }
        int ans = 0;
        int ans1,ans2;
        for(int i = 0;i<n;i++)
        {
            for(int j = 0;j<n;j++)
            {
                if(dp[i][j]>ans)
                {
                    ans = dp[i][j];
                    ans1 = a[i];
                    ans2 = a[j];
                }
            }
        }
        printf("%d\n",ans);
        stack <int> s;
        s.push(ans2);
        s.push(ans1);
        for(int i = 3;i<=ans;i++)
        {
            ans1 = ans2-ans1;
            ans2 = ans2-ans1;
            s.push(ans1);
        }
        int first=1;
        while(!s.empty())
        {
            if(first)
            {
                first = 0;
                printf("%d",s.top());
            }else printf(" %d",s.top());
            s.pop();
        }
        printf("\n");

    }
    return 0;
}