P1763 埃及分数 迭代加深搜索加剪枝

题目链接

---

先来个迭代搜索的模板

int num;//num是当前的限定搜索层数
bool dfs(int step){//step代表当前层数，从0开始
	if(step==num){
		if(到了限定层数但是没达到目标数)return 0;//剪枝
		//中间可以加一些处理，比如同一个限定层数但是有多个答案，我们找最优解
	 	return 1;//否则返回1；
	}
   else{
	for(搜索范围){//一般这里的搜索范围需要根据题目条件手动压缩范围剪枝
	if(范围数合法)一些处理或剪枝；
	if(dfs(step+1)==1)return 1;//向下一层寻找
	
	
}

}
	return 0;
}
int main(){
	for(num=起点;;num++){
    if(dfs(0)==1){break};
    }
    
    //输出答案；
}

---

思路：

回到正题，本题的考察点无非有以下几点，1.分数的减法与化简。2.当前剩余寻找分数个数的极限满足答案的值（用来剪枝）。3.相同限定层数下多个答案的最优解处理。直接上代码。

#include<stdio.h>
#include<math.h>
#include<string.h>
long long a,b,ans[10000],a1[10000],num;
long long gcd(long long k1,long long k2){
	if(k2>k1){
		long long remain=k1;
		k1=k2;
		k2=remain;
	}
	while(k1%k2!=0){
		long long remain=k1%k2;
		k1=k2;
		k2=remain;
	}
	return k2;
}
int dfs(int step,int lim_step,long long remain_a,long long remain_b){//step从0开始， 
	//printf("%d %d %d %d\n",step,lim_step,remain_a,remain_b);
	if(step==lim_step){
		if(remain_a!=0||remain_b>1e7)return 0;
		if(a1[step]<ans[step]){
			for(int i=1;i<=step;i++){//当前最优解的替换
				ans[i]=a1[i];
			}
		}
		return 1;//
	}
	else{
		bool flag=0;
		int beg=ceil(1.0*remain_b/remain_a);
		int remain_c=beg;
		if(beg<=a1[step]){
			beg=a1[step]+1;
		}
		long long end=remain_c*(num-step);//当前的极限值，即后面所有层数的数不递减才能勉强合法的边界
		if(end>1e7){
			end=1e7;
		}
		//printf("%d\n",beg);
		for(int i=beg;i<=end;i++){
			long long remain_a1=0,remain_b1=0;
			long long gcd1=gcd(i,remain_b);
			remain_b1=remain_b*i/gcd1;
			remain_a1=remain_a*(remain_b1/remain_b)-remain_b1/i;
			//printf("%lld %lld\n",remain_a1,remain_b1);
			a1[step+1]=i;
		if(dfs(step+1,lim_step,remain_a1,remain_b1)==1){
			flag=1;//这样可以保证不会找到一个答案就立马返回不继续寻找了
		}
		}
		return flag;
	}
 	
 }
int main(){
	scanf("%lld%lld",&a,&b);
	memset(ans,127,sizeof(ans));
	for(num=1;;num++){
		if(dfs(0,num,a,b)==1){
			break;
		}
	}
	for(int i=1;i<=num;i++){
		printf("%lld ",ans[i]);
	}
	return 0;
}