题目描述

Description

给出一个正整数x，问x最少能由多少个Fibonacci数加减算出。
例如1070=987+89-5-1，因此x=1070时答案是4。

Input

第一行一个正整数q (q<=10)，表示有q组输出。
下面q行每行一个正整数x (x<=4*10^17)。

Output

输出q行，依次表示每个输出的答案。

Sample Input

1
1070

Sample Output

4

题目分析

这题可以记忆化搜索
预处理出斐波那契数列后 每次寻找前驱后继递归计算答案

#include <cstdio>
#include <cstring>
#include <set>
#include <map>
#include <vector>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m;
long long fib[2000];
map<long long,int> dp;
int tot;
int getans(long long x)
{
    if(dp[x]) return dp[x];
    int tmp=lower_bound(fib+1,fib+tot+1,x)-fib;
    return dp[x]=min(getans(x-fib[tmp-1]),getans(fib[tmp]-x))+1;
}
int main()
{
    fib[++tot]=1,fib[++tot]=2;
    dp[1]=dp[2]=1;
    while(1)
    {
        fib[++tot]=fib[tot-1]+fib[tot-2];
        dp[fib[tot]]=1;
        if(fib[tot]>1000000000000000000ll) break;
    }
    scanf("%d",&n);
    while(n--)
    {
        long long x;
        scanf("%lld",&x);
        printf("%d\n",getans(x));
    }
    return 0;
}