生活随笔
收集整理的這篇文章主要介紹了
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的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
