一、题意

埃及分数问题。
给一个分数a/b。
将它拆成式子：a/b=1/c1+1/c2+1/c3...
其中c1,c2,c3,...严格递增，且尽可能使得项数最少，在此前提下最大的c值最小。
输出式子。

二、解析

一般来说枚举题理论上可以用回溯法解决，但是在这题中，我们可以发现回溯法每一层的枚举数量为无限...这个时候我们就要使用迭代加深搜的方法了，或者说使用IDA*算法。
也就是枚举深搜的最大深度maxd，然后在maxd的限制下去进行dfs，并利用maxd来对dfs进行剪枝，使得dfs的每一层可以很快枚举完。
每次针对一个maxd进行dfs时，实际上就是相当于反复去解答这道题，因此也要重新初始化。
由于需要由maxd限制递归层数，因此dfs函数的参数必须包括一个idx表示当前递归的层数，在这题中就是当前正在考虑的式子中的第几项。
剩下的参数就按照需要，比如这题中需要维护剩余分数和，也即a和b的值，然后为了使得下一层枚举的初始值c要比上一层大，还需要增加另一个参数prev_c。

三、代码

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
using LL = long long;
const LL maxn = 1000;
LL kase, a, b, k, ans[maxn], v[maxn];
vector<LL> forbid;

LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}

bool isBetter(LL n) {
    LL i = n - 1;
    for(; i >= 0; i --) if(v[i] != ans[i]) break;
    return ans[i] == -1 || v[i] < ans[i];
}

bool dfs(int maxd, int idx, LL a, LL b, LL prev_c) {
    if(idx == maxd) {
        if(a) return 0;
        if(isBetter(idx)) memcpy(ans, v, sizeof(LL) * idx);
        return 1;
    }
    bool ok = 0;
    for(LL c = max(prev_c + 1, (b % a ? b / a + 1 : b / a)); ; c ++) {
        if(find(forbid.begin(), forbid.end(), c) != forbid.end()) continue;
        if((a * c - b) * (c + 1) > b * c * (maxd - idx - 1)) break;
        v[idx] = c;
        LL na = a * c - b, nb = b * c, t = gcd(na, nb);
        if(dfs(maxd, idx + 1, na / t, nb / t, c)) ok = 1;
    }
    return ok;
}

int main() {
    cin >> kase;
    for(int K = 1; K <= kase; K ++) {
        forbid.clear();
        cin >> a >> b >> k;
        while(k --) {
            LL x;
            cin >> x;
            forbid.push_back(x);
        }
        for(int maxd = 1; ; maxd ++) {
            memset(ans, -1, sizeof(ans));
            if(dfs(maxd, 0, a, b, 0)) break;
        }
        cout << "Case " << K << ": " << a << "/" << b;
        for(int i = 0; ans[i] != -1; i ++) cout << (i ? "+" : "=") << "1/" << ans[i];
        cout << endl;
    }
}

四、归纳

  • gcd的写法要牢记...不要再写错了，就是一句话 return b == 0 ? a : gcd(b, a % b);
  • 一般回溯法可以解决的问题，但是回溯时枚举边界无法确定时，可以使用IDA*算法