E - 菲波拉契数制

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
Submit Status

我们定义如下数列为菲波拉契数列:

F(1)=1

F(2)=2

F(i)=F(i−1)+F(i−2)(i>=3)

给定任意一个数,我们可以把它表示成若干互不相同的菲波拉契数之和。比如13有三种表示法

13=13

13=5+8

13=2+3+8

现在给你一个数n,请输出把它表示成若干互不相同的菲波拉契数之和有多少种表示法。

Input

第一样一个数T,表示数据组数,之后T行,每行一个数n。

T≤105

1≤n≤105

Output

输出T行,每行一个数,即n有多少种表示法。

Sample input and output

6
1
2
3
4
5
13
1
1
2
1
2
3

解题思路:

我们令f( i , j ) 表示对于数 i , 考虑前 j 个斐波那契数,有多少种方案数,采用记忆化搜索,转移方程不再累述

<问题转换为了01背包问题>

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
typedef long long ll;
using namespace std;
const int maxn = 1e5 + ;
int g[],f[maxn][]; int init_g(int cur)
{
if (g[cur] != -)
return g[cur];
int & ans = g[cur] = ;
if (cur == )
return ans = ;
if (cur == )
return ans = ;
return ans = init_g(cur-) + init_g(cur-);
} int dp(int cur,int maxarrive)
{
if (f[cur][maxarrive] != -)
return f[cur][maxarrive];
int & ans = f[cur][maxarrive] = ;
if (cur == )
return ans = ;
for(int i = maxarrive ; i >= ; -- i)
{
if (cur >= g[i])
ans += dp(cur-g[i],i-);
}
return ans;
} int main(int argc,char *argv[])
{
int Case;
memset(g,-,sizeof(g));
memset(f,-,sizeof(f));
init_g(); //初始化斐波那契
scanf("%d",&Case);
while(Case--)
{
int n;
scanf("%d",&n);
printf("%d\n",dp(n,));
}
return ;
}
04-30 19:45