[LeetCode873]Length of Longest Fibonacci Subsequence

Posted on | In

考试的时候这道题直接看错了题意，后来看懂了之后就直接不会做

因为是$Fibonacci$，所以考虑$DP$

可以设$F$$[$$i$$]$$[$$j$$]$为以$C$$[$$i$$]$为当前数，以$C$$[$$j$$]$为当前倒数第一个数的最大长度

我们可以考虑枚举$i$、$j$、$k$

如果$C$$[$$i$$]$$=$$C$$[$$j$$]$$+$$C$$[$$k$$]$

那么转移合法，$F$$[$$i$$]$$[$$j$$]$$=$$max$$($$F$$[$$i$$]$$[$$j$$]$$,$$F$$[$$j$$]$$[$$k$$]$$+$$1$$)$

但是这样的复杂度就是$O$$($$n^3$$)$的，那么考虑优化

如果枚举$i$、$j$，那么$C$$[$$k$$]$$=$$C$$[$$i$$]$$-$$C$$[$$j$$]$是固定的

这里可以离散化和二分查找，时间复杂度是$log$级别的

然后再用$G$$[$$j$$]$$[$$i$$]$表示对于$C$$[$$k$$]$的最大值即可

那么总时间复杂度就是$O$$($$n^2$$logn$$)$的

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
#include<bits/stdc++.h>
using namespace std;
int m,n,ans;
int a[3333];
int b[3333];
int c[3333];
int f[3333][3333];
int g[3333][3333];
inline int read()
{
    char ch=getchar();int c=0,f=1;
    while(!isdigit(ch)) { if(ch=='-') f=0; ch=getchar(); }
    while(isdigit(ch)) c=(c<<3)+(c<<1)+(ch^'0'),ch=getchar();
    return f?c:-c;
}
inline int Half(int z)
{
    int l=1,r=m,mid;
    while(l<=r)
    {
        mid=(l+r)>>1;
        if(a[mid]>z) r=mid-1;
        else if(a[mid]<z) l=mid+1;
        else return mid;
    }
    return 0;
}
int main()
{
    n=read();
    for(register int i=1;i<=n;++i) c[i]=read(),b[i]=c[i];
    sort(b+1,b+n+1);a[++m]=b[1];
    for(register int i=2;i<=n;++i)
    {
        if(b[i-1]==b[i]) continue ;
        a[++m]=b[i];
    }
    for(register int i=2;i<=n;++i)
        for(register int j=1;j<i;++j)
        {
            f[j][i]=2;
            int k=Half(c[i]-c[j]);
            int l=Half(c[j]);
            f[j][i]=max(f[j][i],g[k][j]+1);
            ans=max(ans,f[j][i]);
            g[l][i]=max(g[l][i],f[j][i]);
        }
    printf("%d\n",ans);
    return 0;
}