Aimee

很显然我们并不知道到底会搜索出多少层

但是最优解一定不会太大

那么迭代加深搜索会是一个好的选择

迭代加深要限制层数，这很显然

那么就此来说，当就剩下一个分数可以选的时候

我们要判断这个分数是不是单位分数，如果他是，再判断一下是不是最优解

这样就解决了dfs中的一半（体积意义上）的问题

if(de==1){
        if(x==1&&y>tem[p]&&(Aimee==0||y<ans[Aimee])){
            Aimee=++p;
            tem[p]=y;
            for(int i=1;i<=Aimee;++i){
                ans[i]=tem[i];
            }
            p--;
            return 1;
        }
        return 0;
    }

为什么每一次都要判断呢，因为求的是当前层数的最优解

dfs的另外一个问题就是怎样向下推导

这里有三个优化

第一个优化

很显然保证字母大小递增

第二个优化

由于优化1可知，我们选的分数越来越小

那也就意味着后面的分数铁定比前面小
所以说当前这个分数的分母为i的话

$frac{1}{i} < frac{x}{y}$

这样取一个最大值就可以知道下界了

第三个优化

取的分数越来越小，那么之后所有的分数之和一定会小于他们都等于当前这个分数

换言之，如果剩下的数都等于当前分数的话，肯定是要大于剩下的分数的数的

那么也就是说，如果$frac{k}{i}>frac{x}{y}$是一定要满足的

不然绝无可能合法

但是这样会损失精度

这很讨厌，那就变成乘法$ky>xi$

剪枝完成

bool dfs(int de,int x,int y,int la){
    if(de==1){
        if(x==1&&y>tem[p]&&(Aimee==0||y<ans[Aimee])){
            Aimee=++p;
            tem[p]=y;
            for(int i=1;i<=Aimee;++i){
                ans[i]=tem[i];
            }
            p--;
            return 1;
        }
        return 0;
    }
    bool key=0;
    for(int i=max(la+1,jdn(x,y));de*y>x*i;++i){
        int yy=y/gcd(y,i)*i;
        int xx=x*(yy/y)-yy/i;
        int gcdd=gcd(xx,yy);
        xx/=gcdd;
        yy/=gcdd; 
        tem[++p]=i;
        if(dfs(de-1,xx,yy,i)) key=1;
        p--;
    } 
    return key;
}

注意一些gcd的小细节以及有可能一开始给了一个埃及分数，那样的话就不能拆分的

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m;
int gcd(int x,int y){
    return y==0?x:gcd(y,x%y); 
}
int p;
int de=1;
int ans[100001];
int Aimee;
int tem[100001];
int jdn(int x,int y){
    for(int i=2;i;++i){
        if(i*x>y)
        return i;
    }
    return 0;
}
void print(){
    for(int i=1;i<=Aimee;++i){
        cout<<ans[i]<<" ";
    }
    return ;
}
bool dfs(int de,int x,int y,int la){
    if(de==1){
        if(x==1&&y>tem[p]&&(Aimee==0||y<ans[Aimee])){
            Aimee=++p;
            tem[p]=y;
            for(int i=1;i<=Aimee;++i){
                ans[i]=tem[i];
            }
            p--;
            return 1;
        }
        return 0;
    }
    bool key=0;
    for(int i=max(la+1,jdn(x,y));de*y>x*i;++i){
        int yy=y/gcd(y,i)*i;
        int xx=x*(yy/y)-yy/i;
        int gcdd=gcd(xx,yy);
        xx/=gcdd;
        yy/=gcdd; 
        tem[++p]=i;
        if(dfs(de-1,xx,yy,i)) key=1;
        p--;
    } 
    return key;
}
int main(){
    scanf("%d%d",&n,&m);
    int gcdd=gcd(n,m);
    n/=gcdd;
    m/=gcdd;
    if(n==1){
        cout<<m;
        return 0;
    }
    while(++de){
        p=0;
        if(dfs(de,n,m,1)){
            print();
            return 0;
        }
    }
    return 0;
}

That's all,thanks。