POJ 1011-Sticks Sticks Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 121990 Accepted: 28247 Description George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero. Input The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero. Output The output should contains the smallest possible length of original sticks, one per line. Sample Input 9 5 2 1 5 2 1 5 2 1 4 1 2 3 4 Sample Output 6 5 Source Central Europe 1995
这个题是个深度搜索的好题目，题目的大意为：将一摞长度相同的棍子随机砍成不同长度的小棍子，问原始棍子的长度是多少。 设要求的原始棍子长度为original_len，砍乱之后，所有小棍子的长度总和为sum，因为原来都是整数根相同长度的棍子，所以sum一定是original_len的整数倍；而且因为棍子是随机砍乱的，所以original_len一定不小于砍乱的小棍子中的最大值。由此可以得出original_len的一个取值范围。然后再利用深度搜索求解。 在做算法题时，搜索题算比较难的了，由于我之前这方面的题练的也比较少，所以dfs的思路不太清晰，后来参考了这篇博文，里面关于剪枝的说明也挺详细的，我理解了他的代码，然后自己重新写了一遍，并在某些细节有所改动。代码如下： [cpp] #include <iostream> #include<algorithm> using namespace std; int total_sticks,n,original_len;//分别表示没截断之前有几根棍子，总的截断的数量，没截断之前每根棍子的长度 int sticks[65];//截断之后每部分的长度 int mark[65];//指示每一段是否搜索过了 void init_mark() { for(int i=0;i<65;i++) mark[i]=0; } bool cmp(int a,int b) { return a>b; } //深度搜索，参数分别表示已经拼接好了几根棍子，当前正在拼接的棍子已经拼了多长了，当前测试的下标 bool dfs(int done_sticks,int done_parts,int pos) { if(done_sticks==total_sticks)//如果所有棍子都拼好了，成功 return true; for(int i=pos+1;i<n;i++)//从pos+1开始测试 { if(mark[i]==1)//如果这根小棍子已经拼过了，则开始下一个 continue; if(done_parts+sticks[i]==original_len)//刚好拼成了一个原始的棍子 { mark[i]=1;//标记 if(dfs(done_sticks+1,0,-1))//继续深度搜索，注意pos=-1，因为之前搜索的时候有些前面的小棍子可能没用上 return true; mark[i]=0;//如果搜索失败，回溯 return false; } else if(done_parts+sticks[i]<original_len) { mark[i]=1; if(dfs(done_sticks,done_parts+sticks[i],i))//继续深度搜索，这时pos=i，因为继续往下搜的过程中，只能越取越小，因为这个时候还没有拼成一个完整的棍子，且之前已经搜过大的了 return true; mark[i]=0;//如果搜索失败，回溯 if(done_parts==0)//如果这根小棍子是某次拼接时的第一个棍子，则失败 return false; while(sticks[i]==sticks[i+1])//否则找下一个小棍子时，跳过数值相同的小棍子，因为肯定失败 i++; } } return false; } int main() { while(cin>>n&&n) { int sum=0; for(int i=0;i<n;i++) { cin>>sticks[i]; sum+=sticks[i];//求和 } sort(sticks,sticks+n,cmp);//按降序排序 for(original_len=sticks[0];original_len<=sum;original_len++) { if(sum%original_len==0)//总和肯定能被原始棍子的长度整除 { total_sticks=sum/original_len; init_mark();//每次都要初始化 if(dfs(0,0,-1))//dfs初始值 { cout<<original_len<<endl; break; } } } } return 0; } [/cpp] 代码都已经做了详细的注释，应该不难看懂，唯一和参考博客不同的地方是进行dfs时初始值的不同，我的是0,0,-1，不知道为什么原博客是1,0,-1，按理说最开始还没有组成一个完整的棍子啊，为什么done_sticks=1呢？ 我的代码提交AC，用时16MS，内存220K。]]>