UESTC_菲波拉契数制 2015 UESTC Training for Dynamic Programming<Problem E>

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 ;

}