题目大意

数列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<iostream>
#include<stdio.h>
#include<cstring>
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<N_res;i++)
		printf("%d ",res[i]);
	printf("0\n");
}

int main()
{
	init();
	input();
	get_f();
	get_res();
	output();
}