题目大意：判断所给的数能不能由斐波那契数组成，如果能输出任意一种组成形式（注意：组成数中不能有相邻的），不能输出-1。
解题思路：暴搜 DFS，注意：不要正方向来（1，2，3，5...）TLE，反方向即可 AC。
AC 代码
#include<bits/stdc++.h> #include<cmath> #define mem(a,b) memset(a,b,sizeof a); using namespace std; typedef long long ll; const int maxn=45; ll a[maxn]; int vis[maxn],num[maxn]; int n,flag,len; void init() { len=flag=0; mem(vis,0); } // sum：n -> 0 // l：记录 num[] 个数 // j：递归 for_i=j 加快速度 // nx：验证是否连续 void dfs(int sum,int l,int j,int nx) { if(sum==0) { flag=1; len=l-1; return; } for(int i=j;i>=1;i--) { if(flag==1) return; if(sum>=a[i]) if(!vis[i] && (l-1==0 || abs(nx-i)!=1)) { vis[i]=1; num[l]=a[i]; dfs(sum-a[i],l+1,i-1,i); vis[i]=0; } } } int main() { a[1]=1; a[2]=2; for(int i=3;i<=maxn;i++) a[i]=a[i-1]+a[i-2]; int T; scanf("%d",&T); while(T-- && ~scanf("%d",&n)) { init(); dfs(n,1,maxn,0); if(flag) { printf("%d=",n); for(int i=len;i>=1;i--) { if(i==len) printf("%d",num[i]); else printf("+%d",num[i]); } puts(""); } else puts("-1"); } return 0; }
