CDOJ--1668

原题链接：http://acm.uestc.edu.cn/problem.php?pid=1668

       由于题目意思指的是将分数拆分成不同的单位分数之和，所以就不用考虑将2/3拆成1/3+1/3这种情况了；又由于好的拆分要求项数即len
要少，最小的项要大，故可以采用迭代加深搜索，按项数不断增大的顺序进行搜索；对每一种len，要用一个数组将其的所有情况记录下来，
但这样太耗空间了，因此将情况保存在ans数组里，然后对ans不断进行更新。具体实现时，要设两个标志flag,flag1,flag用来判断是不是
第一次搜索len长的拆分，flag1用来判断是否需要对ans进行更新。还有就是每次搜索的起点要弄好，后面的要比前面的大，要将a/b-1/z作
为新的搜索分数，其中z为当前搜到的符合要求的项。然后就可以比较方便地实现了。

1 #include<stdio.h> 2 3 #include<string.h> 4 5 typedef long long ll; 6 ll a,b,pre[1005],ans[1005]; 7 int flag; 8 ll max(ll x,ll y) 9 { 10 if(x>y)return x; 11 return y; 12 } 13 ll gcd(ll small,ll big) 14 { 15 ll temp; 16 if(big<small) 17 { 18 temp=big;big=small;small=temp; 19 } 20 if(big%small==0)return small; 21 return gcd(big%small,small); 22 } 23 void ids(ll x,ll y,int len,int cur) 24 { 25 ll i,j,k; 26 if(cur==len) 27 { 28 if(x==1) 29 { 30 pre[len]=y; 31 if(!flag) 32 { 33 for(i=1;i<=len;i++) 34 ans[i]=pre[i]; 35 } 36 else 37 { 38 int temp,flag1=0; 39 for(temp=len;temp>0;temp--) 40 { 41 if(pre[temp]>ans[temp])break; 42 if(pre[temp]<ans[temp])flag1=1; 43 if(flag1)break; 44 } 45 if(flag1) 46 { 47 for(i=1;i<=len;i++) 48 ans[i]=pre[i]; 49 } 50 } 51 flag=1; 52 } 53 return ; 54 } 55 j=y/x; 56 if(j<2)j=2; 57 j=max(pre[cur-1]+1,j); 58 while(x*j-y<=0)j++; 59 while(1) 60 { 61 ll z=x*j-y; 62 ll m=y*j; 63 k=gcd(z,m); 64 z/=k;m/=k; 65 if(len-cur<(z*j)/m)return ; 66 if(z*j>=(len-cur)*m)return ; 67 pre[cur]=j; 68 ids(z,m,len,cur+1); 69 j++; 70 } 71 } 72 int main() 73 { 74 int i,j,T; 75 ll k; 76 scanf("%d",&T); 77 while (T--) 78 { 79 scanf("%lld%lld",&a,&b); 80 k=gcd(a,b); 81 a/=k;b/=k; 82 pre[0]=1; 83 for(i=1;i<=1000;i++) 84 { 85 flag=0; 86 ids(a,b,i,1); 87 if(flag)break; 88 } 89 for(j=1;j<=i;j++) 90 printf("%lld ",ans[j]); 91 printf("\n"); 92 } 93 return 0; 94 }

 

转载于:https://www.cnblogs.com/i-love-acm/archive/2013/05/25/3099222.html

总结

以上是生活随笔为你收集整理的CDOJ--1668的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。