题目背景

无

题目描述

已知任意一个正整数都可以拆分为若干个斐波纳契数，现在，让你求出n的拆分方法

输入输出格式

输入格式：
一个数t，表示有t组数据 接下来t行，每行一个数n（如题） 输出格式：
t行，每行一个字符串，表示拆分方法（格式:n=a1+a2+a3+..+an），要求从小到大输出

输入输出样例

输入样例#1：
input1:1 1 input2:1 10 输出样例#1：
output1:1=1; output2:10=2+8;

说明

若有多组数据，以个数最小的为准，若仍有多组，输出右边尽量大的一组 对于100%的数据 t<=1000 1<=n<=10^9

由于答案具有单调性，搜索应该比较快。 做这题之前，还专门打了一张斐波那契数列的表，觉得不会爆int，结果爆了，被坑了33分。 一定要开够。 一定要开够。 一定要开够。 其实这题是个大水题。
#include #include using namespace std; int t,ans,tmp[100005],res[100005]; long long n,f[1005]; void dfs(int cnt,long long lft,int lst) { if(cnt>=ans) return ; if(lft==0) { ans=cnt-1; for(int i=1;i<=ans;i++) res[i]=tmp[i]; } for(int i=lst;i>=1;i--) if(f[i]<=lft) { tmp[cnt]=i; dfs(cnt+1,lft-f[i],i); } } int main() { f[1]=f[2]=1; for(int i=3;i<=50;i++) f[i]=f[i-1]+f[i-2]; scanf("%d",&t); while(t--) { scanf("%lld",&n); ans=1e9+7; dfs(1,n,50); printf("%lld=",n); for(int i=ans;i>=2;i--) printf("%lld+",f[res[i]]); printf("%lld ",f[res[1]]); } return 0; }