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 Input	Sample Output
61234513	112123

 

分析：看作01背包问题，dp[i][j]表示决策第i个斐波那契数，当前数字大小为j时最多的表示方法，有两种转移，状态转移方程有dp[i][j]=dp[i-1][j-fib[i]]+dp[i-1][j];要保证表示的唯一性，dp[i-1][j-fib[i]]和dp[i-1][j]就不能有重复，边界条件为dp[i][fib[i]]=1;另外还可以用滚动数组优化空间复杂度。

写的时候滚动数组写挂过几次，原因是没有注意边界和边界条件，写滚动数组的时候边界条件不能写dp[fib[i]]=1，而是dp[0]=1,dp[1]=1;原因是在第i层决策的时候出现了第i+1的状态，导致重复。

 

#include 
       
        #include 
        
         const int maxn=1e5+1;const int INF=1e5;int fib[25];int sum[25];int dp[25][maxn];void get_fibs(){  fib[0]=1;fib[1]=1;  for(int i=2;i<25;i++)    fib[i]=fib[i-1]+fib[i-2];}void get_sum(){  sum[1]=fib[1];  for(int i=2;i<25;i++)    sum[i]+=sum[i-1]+fib[i];}void get_Dp(){  int i,j;  for(i=1;i<25;i++)    dp[i][0]=1;  dp[1][fib[1]]=1;  for(i=2;i<25;i++)    for(j=0;j<=sum[i]&&j
         
          =fib[i])dp[i][j]=dp[i-1][j-fib[i]]+dp[i-1][j];        else dp[i][j]=dp[i-1][j];}int main(){  //freopen("Ein.txt","r",stdin);  //freopen("out.txt","w",stdout);  get_fibs();  get_sum();  get_Dp();  int T,n,i,Max;  scanf("%d",&T);  while(T--)  {  //Max=-INF;    scanf("%d",&n);  //  for(i=1;i<25;i++)  //    Max=std::max(Max,dp[i][n]);    printf("%d\n",dp[24][n]);  }  return 0;}