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