| 网站首页 | 业界新闻 | 群组 | 交易 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
共有 212 人关注过本帖
标题:求助一道题目
只看楼主 加入收藏
bytton
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2018-12-19
结帖率:100%
  已结贴   问题点数:20  回复次数:6   
求助一道题目
题目如下:
有T 个case ,每个 case 给出一个长度为n 的原数组f[]。从中选出 k 个值组成一个新的数组a[],满足如下规律:
1、    a[i]>0;
2、    当i>2时,a[i]=a[i-1]+a[i-2];
现在要求出最大的 k;
输入格式:
第一行输入一个T, 表示case 的数量。
接下来每两行表示一个case
每个case 第一行有1个数n,表示原数组长度
接下来一行有n个数f[i],对应原数组中的元素

数据规模:
1 <= T <= 302
1 <= n <= 200
0 <= ai <= 10^9
∑n <= 30000

输出格式:
输出T行, 每行1个整数表示最大的k。
输入样例:
3
3
1 2 3
7
6 5 4 3 2 1 1
1
123456
输出样例:
3
5
1
2018-12-19 10:35
bytton
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2018-12-19
  得分:0 
程序代码:
#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。请求支援
2018-12-19 10:37
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:279
帖 子:6062
专家分:34798
注 册:2011-1-18
  得分:20 
你不肯贴题目,我在网上找了个类似的:https://leetcode.com/problems/length-of-longest-fibonacci-subsequence/
(当然,只是类似而已,长度小于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;
    }
};

2018-12-19 12:52
bytton
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2018-12-19
  得分:0 
回复 3楼 rjsp
学校内部题,网上搜不到的
2018-12-19 13:29
bytton
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2018-12-19
  得分:0 
回复 3楼 rjsp
版主,能简单讲解下么,不太看得懂你的代码
2018-12-19 13:43
rjsp
Rank: 20Rank: 20Rank: 20Rank: 20Rank: 20
等 级:版主
威 望:279
帖 子:6062
专家分:34798
注 册:2011-1-18
  得分:0 
回复 5楼 bytton
算法很简单:先排序,然后任取两个数作为 斐波那契数列 的前两个,看看最长是多少。
当然,这个算法不好,里面有些重复的
2018-12-19 14:23
bytton
Rank: 1
等 级:新手上路
帖 子:5
专家分:0
注 册:2018-12-19
  得分:0 
这个我也想到了,我想问一下,我上面的那个动态规划代码有什么问题吗?
2018-12-19 14:42







关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.040779 second(s), 9 queries.
Copyright©2004-2019, BCCN.NET, All Rights Reserved