L - 菲波拉契数制升级版

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

Submit Status

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

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

现在给你一个数

Input

第一样一个数

Output

输出

Sample input and output

Sample Input	Sample Output
61234513	112123

解题思路:

首先高位到低位贪心得到基础情况（最好，因为留了最多的操作空间)

dp(i,j) 表示正在决策第 i 位 ( 后面的已经决策完毕 )，且是否取 0->不取，1->取

dp(i,1) = dp(i-1,0) + dp(i-1,1) //取，转移到i-1

不取,那么这一位斐波那契由前面的相加得到

前面一位取了: 因为不能有相同，所以只能分解成 (x-1) / 2 (少了个0) 种情况( x 是前面0的个数 ) -> 00001 -- 00110 -- 11010

前面一位没取: 因为不能有相同，所以只能分解成 x / 2 种情况.

dp(i,0) = dp(i-1,1) *(A-1) + dp(i-1,0) * A;

#include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #define pb push_backtypedef long long ll;using namespace std;const int maxn = 100;ll f[maxn];int dp[maxn][2];vector
            
             st;void init_f(){ f[0] = 0 , f[1] = 1 , f[2] = 2; for(int i = 3 ; i <= 90 ; ++ i) f[i] = f[i-1] + f[i-2];}int main(int argc , char *argv[]){ init_f(); int Case; scanf("%d",&Case); while(Case--) { st.clear(); memset(dp,0,sizeof(dp)); ll beg; scanf("%lld",&beg); int pos = 88; while(beg) { if (beg >= f[pos]) // Choose { st.pb(pos); beg -= f[pos]; } pos--; } st.pb(0); reverse(st.begin(),st.end()); //高位到低位dp dp[0][1] = 1; //初始化最高位取1有一种情况. for(int i = 1 ; i < st.size() ; ++ i) { dp[i][1] = dp[i-1][0] + dp[i-1][1]; int zeronum = st[i] - st[i-1] ; dp[i][0] = dp[i-1][1] * ( (zeronum-1) / 2 ) + dp[i-1][0] * (zeronum / 2); //注意加括号，不然出问题! } printf("%d\n",dp[st.size()-1][0] + dp[st.size()-1][1]); } return 0;}