求助一道题目 - 编程论坛

#2

bytton2018-12-19 10:37

程序代码：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int f[210];
int dp[210][210];
int BinarySearch(int a[], int L, int R, int tgt)
{
    int Mid;
    while (L<=R)
    {
        Mid = L+(R-L)/2;
        if (a[Mid]==tgt)
        {
            return Mid;
        }
        else if (a[Mid]>tgt)
            R = Mid-1;
        else
            L = Mid+1;
    }
    return -1;
}
int main(void)
{
    //freopen("haha.txt","r", stdin);
    int T;
    scanf("%d", &T);
    while (T--)
    {
        memset(f, 0, sizeof(f));
        memset(dp, 0, sizeof(dp));
        int n, tmax = 2;
        scanf("%d", &n);
        for (int i=0; i<n; ++i)
        {
            scanf("%d", &f[i]);
            if (f[i]<=0)
            {
                i--, n--;
            }
        }
        if (n<=2)
        {
            printf("%d\n", n);
            continue;
        }
        sort(f, f+n);
        for (int i=0; i<n; ++i)
        {
            for (int j=i+1; j<n; ++j)
            {
                dp[i][j] = 2;
            }
        }
        for (int i=0; i<n; ++i)
        {
            for (int j=i+1; j<n; ++j)
            {
                int k = BinarySearch(f, 0, n-1, f[i]+f[j]);
                if (k==-1) continue;
                else
                {
                    if (dp[j][k]<dp[i][j]+1)
                        dp[j][k] = dp[i][j]+1;
                    if (tmax<dp[j][k])
                        tmax = dp[j][k];
                }
            }
        }
        printf("%d\n", tmax);
    }
    return 0;
}

这是我的代码，但是过不了OJ。请求支援

#3

rjsp2018-12-19 12:52

你不肯贴题目，我在网上找了个类似的：https://
（当然，只是类似而已，长度小于3时，leecode要求输出0）

用如下代码，提交成功

程序代码：

class Solution
{
public:
    int lenLongestFibSubseq(vector<int>& A) {
        return foo(A);
    }
private:
    size_t bar( const int* pa, const int* pb, int a, int b )
    {
        size_t len = 0;
        for( ; pa=std::lower_bound(pa,pb,a+b), pa!=pb && *pa==a+b; ++pa )
        {
            ++len;
            b = b+a;
            a = b-a;
        }
        return len==0 ? 0 : 2+len;
    }
    size_t foo( vector<int>& buf )
    {
        size_t maxlen = 0;

        sort( buf.begin(), buf.end() );
        for( size_t i=0; i!=buf.size(); ++i )
            for( size_t j=i+1; j!=buf.size() && j<buf.size()-maxlen+1; ++j )
                maxlen = std::max( maxlen, bar(&buf[0]+i,&buf[0]+buf.size(),buf[i],buf[j]) );

        return maxlen;
    }
};

#4

bytton2018-12-19 13:29

回复 3楼 rjsp

学校内部题，网上搜不到的

#5

bytton2018-12-19 13:43

回复 3楼 rjsp

版主，能简单讲解下么，不太看得懂你的代码

#6

rjsp2018-12-19 14:23

回复 5楼 bytton

算法很简单：先排序，然后任取两个数作为斐波那契数列的前两个，看看最长是多少。
当然，这个算法不好，里面有些重复的

#7

bytton2018-12-19 14:42

这个我也想到了，我想问一下，我上面的那个动态规划代码有什么问题吗？