[CF][225B][贪心] Well-known Numbers

题目大意

数列k-bonacci (k is integer, k > 1)的定义如下：

F(k, n) = 0, for integer n, 1 ≤ n < k;
F(k, k) = 1;
F(k, n) = F(k, n - 1) + F(k, n - 2) + … + F(k, n - k), for integer n, n > k.

给出一个整数s，在数列中找出几个不同的元素使其和等于s。

思路

我们可以先暴力求出所有值小于s的元素，由题目input中给出的数据范围(1 ≤ s, k ≤ 10^9; k > 1)可以推知小于s的元素的数量不会很多。

求取结果是一个贪心的过程。由大到小遍历元素，如果当前元素不大于s，则将s减去此元素，并将此元素作为结果记录下来。重复上述步骤直至s等于0。

代码

#include
#include
#include
using namespace std;

int f[100],res[100];
//f[i]表示f(k,k+i-1)
//res[]存储结果 
int N_f,N_res;
//N_f表示f[]中元素的数量
//N_res表示res[]中元素的数量 
int s,k;

void init()
//初始化 
{
    memset(f,0,sizeof(f));
    memset(res,0,sizeof(res));
}

void get_f()
//计算f[] 
{
    f[1]=1;
    //f(k,k)=1
    for(N_f=2;f[N_f-1]<=s;N_f++)
    //f[]中元素的值最大不超过s 
        for(int i=N_f-1;i>=1&&i>=N_f-k;i--)
            f[N_f]+=f[i];
}

void get_res()
//计算res[] 
{
    for(int i=N_f-1;i>=1&&s;i--)
        if(f[i]<=s)
        {
            res[N_res++]=f[i];
            s-=f[i];
        }
}

void input()
//输入 
{
    scanf("%d%d",&s,&k);
}

void output()
//输出
//每次都在结果末尾加一个0，避免结果数不足2的情况发生。 
{
    printf("%d\n",N_res+1);
    for(int i=0;i

发表回复取消回复