bzoj 2796: [Poi2012]Fibonacci Representation

结论貌似是，，，肯定只有没有重复的数字。http://hzwer.com/6426.html

一开始猜的是贪心，感觉也是可以的啊。。。（想想都有道理，然而看到是神奇的（dp类）记忆化搜索，直接虚的不敢写。。）

 1 #include <bits/stdc++.h>
 2 #define LL long long
 3 #define lowbit(x) x&(-x)
 4 #define inf 2e18
 5 using namespace std;
 6 inline LL ra()
 7 {
 8     LL x=0,f=1; char ch=getchar();
 9     while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
10     while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
11     return x*f;
12 }
13 LL f[805],n;
14 int top,P;
15 map<LL, int > F;
16 int solve(LL x)
17 {
18     if (F[x]) return F[x];
19     int t=lower_bound(f,f+top,x)-f;
20     if (f[t]==x) return 1;
21     return F[x]=min(solve(x-f[t-1]),solve(f[t]-x))+1;
22 }
23 int main()
24 {
25     f[0]=0; f[1]=1;
26     for (int i=2; f[i-1]<=inf; i++,top++) f[i]=f[i-1]+f[i-2];
27     P=ra();
28     for (int i=1; i<=P; i++)
29         printf("%d
",solve(ra()));
30     return 0;
31 }