BZOJ2796: [Poi2012]Fibonacci Representation 暴力

题解:

感觉上暴力好像是卡不掉的，但是我并不知道为什么。

感觉有点虚于是预处理了500W的一个表。

于是就这样过了。

代码:

#include<cstdio>
#include<cctype>
#include<climits>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<map>
using namespace std;

typedef long long ll;
ll f[110];

map<ll,int>M;

int c[5000010];
inline int solve(ll x){
	int n=upper_bound(f+1,f+89,x)-f;
	if(x==f[n-1])
		return 1;
	else
		return min(c[x-f[n-1]],c[f[n]-x])+1;
}
inline int Solve(ll x){
	if(x<=5000000)
		return c[x];
	int n=upper_bound(f+1,f+89,x)-f;
	if(x==f[n-1])
		return 1;
	else
		return min(Solve(x-f[n-1]),Solve(f[n]-x))+1;
}
int main(){
	int i,j;
	for(f[1]=1,f[2]=2,i=3;i<=88;++i)
		f[i]=f[i-1]+f[i-2];
	for(i=1;i<=5000000;++i)
		c[i]=solve(i);
	int T;
	cin>>T;
	ll n;
	while(T--){
		cin>>n;
		cout<<Solve(n)<<endl;
	}
	return 0;
}