2018.8.23 2018暑假集训之埃及分数

发布日期:2019-01-10

题目传送门

主要利用这道题演示一下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 stdinline long long read(){ long long f=1ans=0char c while(c<"0"||c>"9"){if(c=="-")f=-1c=getchar()} while(c>="0"&&c<="9"){ans=ans*10+c-"0"c=getchar()} return f*ans}long long ablong long deeplong long x[1001]long long cx(double x){ if(int(x)==x) return int(x) return int(x)+1}long long gcd(long long along long b){ if(b==0) return a return gcd(ba%b)}bool f=falselong long xx[1001]void dfs(long long belong long anslong long fzlong 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=1i<=ansi++) xx[i]=x[i] } return } for(long long i=max(be+1cx(fm*1.0/fz))i<=cx(fm*1.0/fz*(deep-ans))i++) { x[ans+1]=i dfs(ians+1i*fz-fmi*fm) }}int main(){ memset(xx127sizeof(xx)) a=read()b=read() long long c=gcd(ab) a/=cb/=c for(deep=0deep<=1000deep++) { dfs(00ab) if(f) break } for(long long i=1i<deepi++) cout<<xx[i]<<" " cout<<xx[deep]}