HOJ1049 SticksAnalysis:This problem demands that we rebuild segments of different lengths into segments of the same length,with no fragments.Obviously,the challenges we are facing here are namely to find all possible lengths and to find the minimum one.With a little effort,we can easily figure out that the potential candidates must be in the range [maxlen,sum],where maxlen is the maximum length of all given segments,and sum represents the sum of them.In addition,potential target length must satisfy that sum%length==0,which is obvious.As a result,we can basically enumerate len from maxlen to sum,and see if each len who divides sum with no remainder can be built num times,with the given segments,where num=sum/len.
Now the task goes down to how to decide whether a certain len can be built up according to the rules above.To reach this,we can use the
Depth-First Search Method.Initially,we store the lengths of the segments in an array named
sticks ,then each time,we search from sticks[0] to sticks[n-1](n denotes the total number of given segments),marking each stick that has been used with another bool array
mark ,and repeat this process until we build exactly num(recall that num=sum/len),or have used up all the segments without achieving this.Since we enumerate len from the smaller value to the larger,we find the answer we want as soon as we get a positive response from the search of the current len.When implementing the search method,we must be very careful about the time limit.Consequently,we must apply some rules that can cut the branches.One thing is that,when one segment has failed to build up the current length we want,segments with the same length should not be considered at all.To easily find segments with the same length,we can sort the
sticks array beforehand,in descending order.See more details in the comments in the code below.
Code:
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 #include<algorithm>
5 #define MAXSIZE 65
6 using namespace std;
7 int rest,sum,num,maxlen,len,n;
8 int sticks[MAXSIZE];
9 bool mark[MAXSIZE],flag;//mark is used to mark if a stick has been used in one selecting process
10 bool cmp(int a,int b)
11 {
12 return a>b;
13 }
14 void dfs(int curnum,int curlen,int index)
15 {
16 if(num==curnum) flag=true;//if we can build up exactly num sticks with length equal to len,we've done
17 else if(curlen==len && rest%len==0)//if we can build another stick with length equal to len,and the remaining
18 //total length can still be divided by len,then we move on,increasing the curnum by 1
19 dfs(curnum+1,0,0);
20 else
21 {
22 for(int i=index,pre=-1;i<n;i++)
23 {
24 if(!mark[i] && sticks[i]!=pre && sticks[i]+curlen<=len)
25 //obviously,if sticks[i] does not work,sticks with the same length cannot work either
26 //so we use pre to record the previous potential one's length,and in case that the current stick
27 //fails the mission,the next stick with the same length won't be tested
28 {
29 pre=sticks[i];
30 mark[i]=true;
31 rest-=sticks[i];
32 dfs(curnum,curlen+sticks[i],i+1);
33 mark[i]=false;
34 rest+=sticks[i];
35 if(flag || !index) return;//if flag==true,it means success,or index==0 denotes failure
36 }
37 }
38 }
39 }
40 int main()
41 {
42 while(scanf("%d",&n)==1 && n)
43 {
44 maxlen=sum=0;flag=false;
45 for(int i=0;i<n;i++)
46 {
47 scanf("%d",&sticks[i]);
48 maxlen=(maxlen>sticks[i]) ? maxlen : sticks[i];
49 sum+=sticks[i];
50 }
51 sort(sticks,sticks+n,cmp);
52 rest=sum;
53 for(len=maxlen;len<=sum;len++)
54 //the potential result can only be in the range [len,sum]
55 {
56 if(sum%len==0)
57 {
58 num=sum/len;
59 memset(mark,0,sizeof(mark));
60 dfs(0,0,0);
61 }
62 if(flag) break;
63 }
64 printf("%d\n",len);
65 }
66 }
67