【Uva 12558】 Egyptian Fractions (HARD version) （迭代加深搜，IDA*）

IDA* 就是iterative deepening（迭代深搜）+A*（启发式搜索）

启发式搜索就是设计估价函数进行的搜索（可以减很多枝哦~）

这题。。。

理论上可以回溯，但是解答树非常恐怖，深度没有明显上界，加数的选择理论上也是无限的。

我们可以从小到大枚举深度maxd，

设计估价函数，当扩展到第i层，前i个分数的和为c/d，第i的分数为1/e，接下来至少需要（a/b+c/d）/（1/e）个分数，如果超过maxd-i+1，那么直接回溯就好了。。

 1 #include<cstdio>
 2 #include<cstdlib>
 3 #include<cstring>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<queue>
 7 #include<cmath>
 8 using namespace std;
 9 #define LL long long
10 #define Maxn 1100
11 
12 LL a,b;
13 LL maxd,ans[Maxn],v[Maxn];
14 
15 bool qq[1010];
16 
17 LL mymax(LL x,LL y) {return x>y?x:y;}
18 
19 bool better(LL d)
20 {
21     for(LL i=d;i>=1;i--) if(v[i]!=ans[i])
22     {
23         return ans[i]==-1||v[i]<ans[i];
24     }
25     return 0;
26 }
27 
28 LL get_first(LL a,LL b)
29 {
30     for(LL i=1;;i++)
31     {
32         if(b<=a*i) return i;
33     }
34 }
35 
36 LL gcd(LL a,LL b)
37 {
38     if(b==0) return a;
39     return gcd(b,a%b);
40 }
41 
42 bool dfs(LL d,LL from,LL aa,LL bb)
43 {
44     if(d==maxd)
45     {
46         if(bb%aa) return 0;
47         v[d]=bb/aa;
48         if(v[d]<=1000&&!qq[v[d]]) return 0;
49         if(better(d)) memcpy(ans,v,sizeof(ans));
50         return 1;
51     }
52     bool ok=0;
53     from=mymax(from,get_first(aa,bb));
54     for(LL i=from;;i++) 
55     {
56         if(i<=1000&&!qq[i]) continue;
57         if(bb*(maxd+1-d)<=i*aa) break;
58         v[d]=i;
59         LL b2=bb*i;
60         LL a2=aa*i-bb;
61         LL g=gcd(a2,b2);
62         if(dfs(d+1,i+1,a2/g,b2/g)) ok=1;
63     }
64     return ok;
65 }
66 
67 int main()
68 {
69     LL T,kase=0;
70     scanf("%lld",&T);
71     while(T--)
72     {
73         scanf("%lld%lld",&a,&b);
74         memset(qq,1,sizeof(qq));
75         LL k;
76         scanf("%lld",&k);
77         for(LL i=1;i<=k;i++)
78         {
79             LL x;
80             scanf("%lld",&x);
81             qq[x]=0;
82         }
83         for(maxd=1;;maxd++)
84         {
85             memset(ans,-1,sizeof(ans));
86             if(dfs(1,get_first(a,b),a,b)) break;
87         }
88         printf("Case %lld: %lld/%lld=",++kase,a,b);
89         printf("1/%lld",ans[1]);
90         for(LL i=2;i<=maxd;i++) printf("+1/%lld",ans[i]);
91         printf("
");
92         /*printf("%d
",maxd);
93         for(LL i=1;i<=maxd;i++) printf("%d
",ans[i]);*/
94     }
95     return 0;
96 }

View Code

话说题目上的hard case我的程序也跑不出来。。。ORZ。。

2016-11-14 20:17:33