主要利用这道题演示一下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]; }