C.菲波拉契数制时间：2s 内存：65536KB我们定义如下数列为菲波拉契数列： F (1) = 1 F (2) = 2 F (i) = F(i-1)+F(i-2) (i>=3)给定任意一个数，我们可以把它表示成若干不同的菲波拉契数之和。比如13有三种表示法13=1313=5+813=2+3+8现在给你一个数n，请输出把它表示成若干不同的菲波拉契数之和有多少种表示法。输入：第一样一个数T，表示数据组数，之后T行，每行一个数n。20%的数据:T<=10,n<=3060%的数据:T<=100,n<=100000100%的数据：T<=10^5, n<=10^18输出：输出T行，每行一个数，即n有多少种表示法。样例：输入：61234513输出：112123
这种DP很不容易看出想出状态，我在考试的时候大部分时间都用在这道题上了，评讲时也证明我基本上已经想了90%的正解，只有一个我没有想到，即最大表示后每一项后移步数不超过1。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<ctime> #include<cmath> #include<algorithm> #include<set> #include<map> #include<vector> #include<string> #include<queue> #include<stack> using namespace std; #ifdef WIN32 #define LL "%I64d" #else #define LL "%lld" #endif typedef long long qword; typedef long long number; #define MAXF 110 #define MAXN 110000 #define PROB "C" qword fib[MAXF]; int topf; vector<int> vec; void init() { int i; fib[0]=fib[1]=1; for (i=2;fib[i-1]<1000000000000000000LL;i++) { fib[i]=fib[i-1]+fib[i-2]; } topf=i-1; } qword f[MAXF][2]; int a[MAXF]; qword n,m; int main() { //freopen("input.txt","r",stdin); //freopen("output.txt","w",stdout); freopen(PROB".in","r",stdin); freopen(PROB".out","w",stdout); int i,j,k; int x,y,z; int nn; scanf("%d",&nn); init(); while (nn--) { scanf(LL ,&n); vec.clear(); for (i=topf;i>0;i--) { if (fib[i]<=n) { n-=fib[i]; vec.push_back(i); } } sort(vec.begin(),vec.end()); for (i=0;i<vec.size();i++) { a[i]=(-((i)?vec[i-1]:1)+vec[i]); } f[0][1]=1; f[0][0]=a[0]/2; for (i=1;i<vec.size();i++) { f[i][0]=((a[i]-1)/2)*f[i-1][1]+((a[i])/2)*f[i-1][0]; f[i][1]=f[i-1][0]+f[i-1][1]; } printf("%lld\n",f[vec.size()-1][0]+f[vec.size()-1][1]); } return 0; }
转载于:https://www.cnblogs.com/mhy12345/p/3960863.html
