IDA* 就是iterative deepening（迭代深搜）+A*（启发式搜索）
启发式搜索就是设计估价函数进行的搜索（可以减很多枝哦~）
这题。。。
理论上可以回溯，但是解答树非常恐怖，深度没有明显上界，加数的选择理论上也是无限的。
我们可以从小到大枚举深度maxd，
设计估价函数，当扩展到第i层，前i个分数的和为c/d，第i的分数为1/e，接下来至少需要（a/b+c/d）/（1/e）个分数，如果超过maxd-i+1，那么直接回溯就好了。。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cmath>
using namespace std;
#define LL long long
#define Maxn 1100 LL a,b;
LL maxd,ans[Maxn],v[Maxn]; bool qq[]; LL mymax(LL x,LL y) {return x>y?x:y;} bool better(LL d)
{
for(LL i=d;i>=;i--) if(v[i]!=ans[i])
{
return ans[i]==-||v[i]<ans[i];
}
return ;
} LL get_first(LL a,LL b)
{
for(LL i=;;i++)
{
if(b<=a*i) return i;
}
} LL gcd(LL a,LL b)
{
if(b==) return a;
return gcd(b,a%b);
} bool dfs(LL d,LL from,LL aa,LL bb)
{
if(d==maxd)
{
if(bb%aa) return ;
v[d]=bb/aa;
if(v[d]<=&&!qq[v[d]]) return ;
if(better(d)) memcpy(ans,v,sizeof(ans));
return ;
}
bool ok=;
from=mymax(from,get_first(aa,bb));
for(LL i=from;;i++)
{
if(i<=&&!qq[i]) continue;
if(bb*(maxd+-d)<=i*aa) break;
v[d]=i;
LL b2=bb*i;
LL a2=aa*i-bb;
LL g=gcd(a2,b2);
if(dfs(d+,i+,a2/g,b2/g)) ok=;
}
return ok;
} int main()
{
LL T,kase=;
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld",&a,&b);
memset(qq,,sizeof(qq));
LL k;
scanf("%lld",&k);
for(LL i=;i<=k;i++)
{
LL x;
scanf("%lld",&x);
qq[x]=;
}
for(maxd=;;maxd++)
{
memset(ans,-,sizeof(ans));
if(dfs(,get_first(a,b),a,b)) break;
}
printf("Case %lld: %lld/%lld=",++kase,a,b);
printf("1/%lld",ans[]);
for(LL i=;i<=maxd;i++) printf("+1/%lld",ans[i]);
printf("\n");
/*printf("%d\n",maxd);
for(LL i=1;i<=maxd;i++) printf("%d\n",ans[i]);*/
}
return ;
}
话说题目上的hard case我的程序也跑不出来。。。ORZ。。
2016-11-14 20:17:33