HDU 5167 Fibonacci 发表于 2016-08-12 | 分类于 DFS | | 阅读次数 DFS模板题 题目链接HDU 5167 题目大意判断一个数是否能分解为多个斐波那契数的乘积。 AC代码123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include<stdio.h>#include<iostream>#include<string.h>#include<algorithm>using namespace std;int a[50];void get() //预处理,得到斐波那契数列{ int i; a[0]=0; a[1]=1; for(i=2;i<50;i++) { a[i]=a[i-1]+a[i-2]; }}int dfs(int n,int pos) //pos记录位置{ if(n==1) //满足条件 { return 1; } for(int i=pos;i>=3;i--) //从pos往前寻找 { if(n%a[i]==0) //满足条件 对该点DFS { if(dfs(n/a[i],i)==1) { return 1; } } } return 0;}int main(){ get(); int m,k; scanf("%d",&m); while(m--) { scanf("%d",&k); if(k==0) { printf("Yes\n"); } else { if(dfs(k,45)==1) { printf("Yes\n"); } else { printf("No\n"); } } } return 0;} 坚持原创技术分享,您的支持将鼓励我继续创作! 赏 微信打赏 支付宝打赏