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

Sample InputSample 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 + 500; int g[31],f[maxn][31]; int init_g(int cur) { if (g[cur] != -1) return g[cur]; int & ans = g[cur] = 0; if (cur == 1) return ans = 1; if (cur == 2) return ans = 2; return ans = init_g(cur-1) + init_g(cur-2); } int dp(int cur,int maxarrive) { if (f[cur][maxarrive] != -1) return f[cur][maxarrive]; int & ans = f[cur][maxarrive] = 0; if (cur == 0) return ans = 1; for(int i = maxarrive ; i >= 1 ; -- i) { if (cur >= g[i]) ans += dp(cur-g[i],i-1); } return ans; } int main(int argc,char *argv[]) { int Case; memset(g,-1,sizeof(g)); memset(f,-1,sizeof(f)); init_g(28); //初始化斐波那契 scanf("%d",&Case); while(Case--) { int n; scanf("%d",&n); printf("%d\n",dp(n,28)); } return 0; }

 

转载于:https://www.cnblogs.com/Xiper/p/4539618.html

相关资源：垃圾分类数据集及代码