[LJOJ1244] 埃及分数

您可以去 Vijos 上搜索此题,不过温馨提示, Vijos 的数据是错的,详情可以参考那题的讨论。

这是一道IDA*经典题,集成了启发式搜索迭代加深的特点进行剪枝。

  • 迭代加深
    本题中,我们限定DFS搜索的层数,如果超过这个层数,就进行剪枝。

  • 启发式搜索
    我们设立一个估价函数,考虑最优情况下的步数。
    本题中我们按照分母从小到大的顺序来DFS埃及分母,所以之后遇到的值就必定大于当前取到的值。
    我们可以通过这个特性来写估价函数,即(a / b) / (1 / u)(其中a / b表示当前的值,u表示剩下能够取到的最小分母)
    做其他题目时一定要注意估价函数所估计的值之多劣于实际情况,而不能比实际情况更优
#include <bits/stdc++.h>
using namespace std;
typedef long long ll; // 用 typedef 据说比 define 快
ll a, b;
int limit;
vector < ll > now, ans; // 存储当前选择的数和答案
void red(ll a, ll b) { // 对分数 a / b 约分
    ll gcd = __gcd(a, b);
    a /= gcd, b /= gcd;
}
int last(ll a, ll b, ll u) { // 估价函数
    return a * u / b;
}
bool better() { // 判断当前情况是否比答案更优
    if (ans.empty()) return true;
    for (vector < ll > ::reverse_iterator i = ans.rbegin(), j = now.rbegin(); i != ans.rend(), j != now.rend(); i++, j++)
        if (*i > *j) return true;
        else if (*i < *j) return false; 
    return false;
}
void DFS(ll a, ll b, int step) { // IDA* 核心代码
    red(a, b);
    if (step == limit) { //如果已经达到了迭代步数限制
        if (a == 1) return; //判断剩余部分是否是埃及分数
        now.push_back(b);
        if (better())
            ans = now;
        now.pop_back();
    }
    ll start = b / a + 1; // 数学方法可以证明至少为这个值
    if (!now.empty())
        start = max(start, *--now.end() + 1);  // 剩余开始枚举的至少从当前决策的最大值 + 1,开始
    for (ll i = start; true; i++) {
        if (step + last(a, b, i) > limit) return;
        now.push_back(i);
        DFS(a * i - b, b * i, step + 1); // 进行下一步
        now.pop_back();
    }
}
int main() {
    scanf("%lld%lld", &a, &b);
    for (limit = 0; true; limit++) { // 实际取到的个数是 limit + 1
        DFS(a, b, 0);
        if (!ans.empty()) {
            for (vector < ll > ::iterator it = ans.begin(); it != ans.end(); it++)
                printf("%lld ", *it);
            break;
        }
    } 
    return 0;
}
添加新评论

0%