BZOJ [Poi2012]Fibonacci Representation

找最近的数

记忆化

(我也不知道为什么对的)

#include<cstdio>

#include<algorithm>

#include<map>

using namespace std;

int q,lim=85,id;

long long F[105];

map<long long,int> M;

int dfs(long long x){

	if (M[x]) return M[x];

	int id1=lower_bound(F+1,F+lim+1,x)-F-1;

	int id2=lower_bound(F+1,F+lim+1,x)-F;

	int ans=0;

	if (x-F[id1]<=F[id2]-x) ans=dfs(x-F[id1])+1;

	else ans=dfs(F[id2]-x)+1;

	M[x]=ans;

	return ans;

}

int main(){

	scanf("%d",&q);

	F[0]=F[1]=1;

	for (int i=2; i<=lim; i++) F[i]=F[i-1]+F[i-2];

	for (int i=1; i<=lim; i++) M[F[i]]=1;

	while (q--){

		long long x;

		scanf("%lld",&x);

		printf("%d\n",dfs(x));

	}

	return 0;

}