题目：
Sticks
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 364 Accepted Submission(s): 116
Problem 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 file contains the smallest possible length of original sticks, one per line.
Sample Input
95 2 1 5 2 1 5 2 141 2 3 40
Sample Output
65
Source
ACM暑期集训队练习赛（七）
Recommend
lcy
题目分析：
DFS。
代码如下：
/* * e.cpp * * Created on: 2015年2月25日 *Author: Administrator */#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int maxn = 65;bool visited[maxn];//用于标记某个木棒是否已经使用过int values[maxn];//结果序列bool flag;//用于标记使用已经成功找到一种方案int parts;//标记木棒的份数int len;//等长木棒的长度int n;//原始木棒序列的根数/** * 深搜。 * pos:当前搜索的的木棒的索引 * cur:当前已经拼成的木棒的长度 * cnt:当前已经拼好的木棒的数量 */void dfs(int pos,int cur,int cnt){if(cur == len){//如果当前木棒的长度==指定的木棒长度cnt++;//拼好的木棒的数量+1if(cnt == parts){//如果拼好的木棒数量==指定的木棒数量flag = true;//将flag标记为true,表示已经成功return ;//返回}//如果还没有拼够指定数量的等长木棒dfs(0,0,cnt);//则继续拼}if(pos >= n){//如果当前搜索到的木棒的索引已经超出了木棒的范围return ;//则返回，，表示没有成功}int i;for(i = pos ; i < n ; ++i){//从当前木棒开始向后扫if(visited[i] == false && values[i] + cur <= len){//如果该根木棒没有被访问过&&当前木棒的长度+已经拼好的木棒的长度<=lenvisited[i] = true;//则将该木棒标记为已经访问过dfs(i+1,values[i]+cur,cnt);//在此基础上继续往下搜visited[i] = false;//回滚/*** 剪枝。* 如果当前已经找到一种方案,则返回* pos的那个剪枝我也还没有想明白,没加的时候TLE.**/if(flag == true|| pos == 0){return ;}}}}int main(){while(scanf("%d",&n)!=EOF,n){int maxLen = -1;int sum = 0;int i;for(i = 0 ; i < n ; ++i){scanf("%d",&values[i]);if(values[i] > maxLen){maxLen = values[i];//计算所有木棒中的最大长度}sum += values[i];//计算所有木棒的总长度}/** * 从单根木棒的最大长度开始枚举所有情况。 * 为什么从但根木棒的最大值开始枚举而不是从最小值开始枚举呢?因为最小值的情况下, * 比最小值长度要大的木棒必然会被废弃.这很明显不符合题意 */for(len = maxLen ; len < sum ; ++len){if(sum%len == 0){//如果该长度下,木棒能够被等分memset(visited,false,sizeof(visited));parts = sum/len;//计算该长度下能分成多少根木棒flag = false;//重新将flag设置成falsedfs(0,0,0);//开始搜索if(flag == true){//如果已经成功break;//跳出循环}}}printf("%d\n",len);//输出找到的合成后的木棒的最小的长度}return 0;}
不会因为别人显赫的成功而促使自己有卓越的进步。
