题目：埃及分数
题目链接：http://codevs.cn/problem/1288/
题目大意：
给出一个分数，由分子a 和分母b 构成，现在要你分解成一系列互不相同的单位分数（形如：1/a，即分子为1），要求：分解成的单位分数数量越少越好，如果数量一样，最小的那个单位分数越大越好。
如：
19/45 = 1/3 + 1/12 + 1/180;
19/45 = 1/5 + 1/6 + 1/18;
以上两种分解方法都要3个单位分数，但下面一个的最小单位分数1/18比上一个1/180大，所以第二个更优。
思路：
虽然是求最优解，但这道明显不是广搜吧（空间要求太高），而且很明显是用深搜做，即从1~无穷，每一个分母，都有选中和不选中两种状态，如果选中，那么就减去这个分数，没有就是跳过，但无穷到底是哪里呢，而且具体要选几个呢，这就是这道题的难点。因为多组答案的优先级是由单位分数的个数首先决定，那么我们可以逐次放宽个数的限制，即迭代加深搜索。
迭代加深搜索的具体内容：第一次，我限制只能用k个单位分数来完成，如果找完所有情况，还是没找到解，那么我现在用k+1个单位分数解决，这样优点如下：
1. 肯定保证最优解，因为我用k个来完成分解就说明比k小的个数分解不出来，如果分解得出来，我在那时就退出循环了。
2. 虽然看似重复进行了很多遍的搜索，但上一层的搜索量和下一层比起来太少了，不影响总的时间复杂度。
抛开逐步解开个数限制外，每一个个数限制下的做法和平常的深入优先搜索大致相同，要注意剪枝！
主要的两个剪枝如下：
1. 限制开头：并不是每次都要从1开始遍历分母，假设现在要分解a/b，那么分母b/a就是起点，因为b/a的分数太大，起始点已经超过了a/b，没有什么意义：1/(b/a)=a/b ，假设起点s<b/a，那么显而易见，起点的分数已经比我们要的总和（a/b）大了。
2. 限制结尾：
（1）比较简单的限制结尾可以这样看：如果我已经找到分母k了，而现在要分解得分数是a/b，现在还要找m个单位分数，那么可以想象：有可能 m * ( 1/k ) 还小于a/b，也就是说就算全是1/k，我凑够m个，也达不到a/b，那么说明前面的分配方案肯定有无，直接可以return了。加上这个剪枝已经可以得到答案了，只是时间有点慢罢了。
（2）现在我们假设终点为t，还要找m个单位分数，现在的分数剩下a/b，那么很容易有m * (1/t) <= a / b ，也就是说我如果m个都用最小的，肯定小于等于a/b。（等于号就是说有可能m=1，我可能直接终点就是答案，如果m>1，那么终点肯定也不可能选到，假设选了（后面还要选（m-1）个，肯定凑不够）这样子，由上面的式子，经过变换，可以得到 t >= m*b/a ，也就是说终点为m*b/a。
有了思路代码还是很容易的：
1 #include<stdio.h> 2 #include<string.h> 3 #include<stdlib.h> 4 5 int gcd(int a,int b) 6 { 7 return b?gcd(b,a%b):a; 8 } 9 10 int ans[1000],ao; 11 int out[1000],oo; 12 13 void dfs(int limit,int h,int ma,int mb) 14 { 15 if(h==limit) return ; 16 if(mb%ma==0 && mb/ma>ans[ao-1] && ( oo<=0 || mb/ma < out[oo-1] )) 17 { 18 ans[ao++]=mb/ma; 19 oo=ao; 20 memcpy(out,ans,sizeof(ans)); 21 ao--; 22 return ; 23 } 24 int i=mb/ma-1; 25 if(i<=ans[ao-1]) i=ans[ao-1]; //ans[ao-1]就是前面找过的最后一个，这前面的都处理过（选中or不选中） 26 int j=(limit-h)*mb/ma; 27 while(++i<=j) 28 { 29 if(oo>0&&i>=out[oo-1]) return ; 30 int g=gcd(i,mb); 31 int k=i/g; 32 //if(ma*i/mb+h>limit) return ; 33 int x=mb*k; 34 int y=ma*k-mb/g; 35 if(y<0) continue; 36 ans[ao++]=i; 37 if(y==0) 38 { 39 oo=ao; 40 memcpy(out,ans,sizeof(ans)); 41 ao--; 42 return ; 43 } 44 dfs(limit,h+1,y,x); 45 ao--; 46 } 47 } 48 49 int main() 50 { 51 int a,b; 52 while(scanf("%d%d",&a,&b)!=EOF) 53 { 54 ao=0; 55 oo=0; 56 for(int i=1;i<100;i++) 57 { 58 //printf("%d ",i); 59 dfs(i,0,a,b); 60 if(oo>0) break; 61 } 62 for(int i=0;i<oo;i++) 63 { 64 if(i!=0) printf(" "); 65 printf("%d",out[i]); 66 } 67 printf(" "); 68 } 69 return 0; 70 }