12558-Egypetian Fractions(HARD version)(IDA*アルゴリズム)

IDA*アルゴリズムは、反復的に検索とA*アルゴリズムの結合を深めます.
反復深度検索は、明確な深さの上限がない問題に適用され、最適解が見つかるまで、深さは小さいから大きいまで列挙され、深度検索の盲目性が低減される.
A*アルゴリズムは楽観的な評価関数が必要です.この関数では一番小さい点を探して検索します.時間の複雑さはこれに浪費されました.
コードは以下の通りです

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,kase=0;
ll v[10000+10],ans[10000+10],a,b,e,k,maxd;
set<ll> g;
bool better(int d) {
    for(int i=d;i>=0;i--) if(v[i] != ans[i]) {
        return ans[i] == -1 || v[i] < ans[i];
    }   return false;
}
ll get_first(ll a,ll b) {
    return b/a + 1;
}
ll gcd(ll a,ll b) {
    return b == 0 ? a : gcd(b, a%b);
}
bool dfs(int d,ll from,ll aa, ll bb) {
    if(d == maxd) {
        if(bb % aa) return false;
        v[d] = bb/aa;
        if(g.count(bb/aa)) return false; //               
        if(better(d)) memcpy(ans,v,sizeof(ll) * (d+1));
        return true;
    }
    bool ok = false;
    from = max(from,get_first(aa,bb));
    for(ll i = from; ; i++) {
        if(g.count(i)) continue;//              
        if(bb * (maxd+1-d) <= i * aa) break; //        
        v[d] = i;
        ll b2 = bb * i;
        ll a2 = aa * i - bb;
        ll g = gcd(a2,b2);
        if(dfs(d+1,i+1,a2/g,b2/g)) ok = true;
    }
    return ok;
}
int main() {
    scanf("%d",&T);
    while(T--) {
        scanf("%lld%lld%lld",&a,&b,&k);
        g.clear();
        for(int i=0;i<k;i++) {
            scanf("%lld",&e);
            g.insert(e);
        }
        for(maxd = 1; ; maxd++) {
            memset(ans,-1,sizeof(ans));
            if(dfs(0,get_first(a,b),a,b))  break;
        }
        printf("Case %d: %lld/%lld=1/%lld",++kase,a,b,ans[0]);
        for(int i=1;i<=maxd;i++) printf("+1/%lld",ans[i]);
        printf("
");
    }
    return 0;
}