您现在的位置是:网站首页> 内容页

2018.8.23 2018暑假集训之埃及分数

  • 百老汇官网
  • 2019-03-10
  • 182人已阅读
简介题目传送门主要利用这道题演示一下dfs如何进行剪枝感谢@si-ri-yangdalao的帮助(1)读入优化这个就不多解释了(2)运算优化利用gcd算法(3)迭代加深大概就是自己

题目传送门

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

 

文章评论

Top