2796: [Poi2012]Fibonacci Representation

Description

给出一个正整数x，问x最少能由多少个Fibonacci数加减算出。

所以说这题的数据不对是吗QAQ，然后就卡了好久。
对于每个数找最近的fib数，然后进行记忆化搜索。正确性我不会证。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int t,tot;
ll fib[100],n;
int f[1001000];
int getid(ll x)
{
    int l=1,r=tot+1,mid;
    while(l<r)
    {
        mid=l+r>>1;
        if(fib[mid]>=x) r=mid;
        else l=mid+1;
    }
    return r;
}
int dfs(ll n)
{
    if(n<=1000000)
    {
        if(f[n]) return f[n];
        int tmp=getid(n);
        if(fib[tmp]==n) return f[n]=1;
        f[n]=min(dfs(fib[tmp]-n),dfs(n-fib[tmp-1]))+1;
        return f[n];
    }
    else
    {
        int tmp=getid(n);
        if(fib[tmp]==n) return 1;
        return min(dfs(fib[tmp]-n),dfs(n-fib[tmp-1]))+1;
    }
}
int main()
{
    scanf("%d",&t);
    fib[2]=1; tot=2;
    while(fib[tot]<=1000000000000000000ll)
    {
        tot++; fib[tot]=fib[tot-1]+fib[tot-2];
    }
    while(t--)
    {
        scanf("%lld",&n);
        printf("%d\n",dfs(n));
    }
    return 0;
}