【bzoj2796】 [Poi2012]Fibonacci Representation

2015年3月12日1,1941

Description

Fib数列0,1,1,2,3,5,8,13,21。

给出一个数字,用FIB数列各项加加减减来得到。例如

10=5+5

19=21-2

17=13+5-1

1070=987+89-5-1

Input

In the first line of the standard input a single positive integer is given (1 <=P<=10) that denotes the number of queries. The following lines hold a single positive integer K each 1<=K<=10^17.

Output

For each query your program should print on the standard output the minimum number of Fibonacci numbers needed to represent the number k as their sum or difference.

Sample Input

1
1070

Sample Output

4
题解
因为F[k]*2=F[k+1]+F[k-2],即存在最优解满足同一个FIB数出现次数不超过1
令l表示小等于n且最大的斐波那契数,r为其后一项,可以暴力或者二分求
dp(n) = min{ dp(n-l) , dp(r-n) } + 1
使用记忆化搜索

 

  • 魔法炮2015年3月28日 下午9:40 回复

    ……我知道了应该把k-1改成k-2

    #1