题目传送门

主要利用这道题演示一下dfs如何进行剪枝

感谢@si-ri-yang dalao的帮助

（1）读入优化 这个就不多解释了

（2）运算优化 利用gcd算法

（3）迭代加深 大概就是自己从小到大（贪心）枚举递归次数（共几个分数）

（4）上下界优化

每个分数分母的下界：上一个分数的分母+1、当前分母除以分子向上取整的最大值

（证明：

　　设待枚举分数为1/t

　　目前剩余分数为a/b

　　已知要求1/t<a/b所以t<b/a

）

　　　　　　   上界：当前分母除以分子乘以剩余递归深度（把之后所有分数累加到当前分数上）

上代码

#include<bits/stdc++.h>using namespace std;inline long long read(){ long long f=1,ans=0;char c; while(c<"0"||c>"9"){if(c=="-")f=-1;c=getchar();} while(c>="0"&&c<="9"){ans=ans*10+c-"0";c=getchar();} return f*ans;}long long a,b;long long deep;long long x[1001];long long cx(double x){ if(int(x)==x) return int(x); return int(x)+1;}long long gcd(long long a,long long b){ if(b==0) return a; return gcd(b,a%b);}bool f=false;long long xx[1001];void dfs(long long be,long long ans,long long fz,long long fm){ if(fz<0) return; if(fm==0) return; if(ans==deep) { if(fz-fm==0||fz==0) { f=true; if(x[ans]<xx[ans]) for(long long i=1;i<=ans;i++) xx[i]=x[i]; } return; } for(long long i=max(be+1,cx(fm*1.0/fz));i<=cx(fm*1.0/fz*(deep-ans));i++) { x[ans+1]=i; dfs(i,ans+1,i*fz-fm,i*fm); }}int main(){ memset(xx,127,sizeof(xx)); a=read(),b=read(); long long c=gcd(a,b); a/=c,b/=c; for(deep=0;deep<=1000;deep++) { dfs(0,0,a,b); if(f) break; } for(long long i=1;i<deep;i++) cout<<xx[i]<<" "; cout<<xx[deep];}