1204 Sticks
时间限制:1000MS 内存限制:10000K提交次数:0 通过次数:0
题型: 外判编程题 语言: 无限制
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
95 2 1 5 2 1 5 2 141 2 3 40
Sample Output
65
//C++答案代码如下：
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
bool anUsed[65];
int L,N,stick[65];
bool cmp(int a,int b)
{
return a>b;
}
bool DFS(int nUnusedSticks,int nLeft)
{
int i,j,k;
if(!(nUnusedSticks||nLeft)) return 1;//假如都为0，则拼合完成
if(!nLeft) nLeft=L;//新建一个要拼合的棍
for(i=0;i<N;++i)
if(!anUsed[i]&&stick[i]<=nLeft){//剪枝
if(i>0&&!anUsed[i-1]&&stick[i]==stick[i-1]) continue;//剪枝
anUsed[i]=1;
if(DFS(nUnusedSticks-1,nLeft-stick[i])) return 1;
anUsed[i]=0;//可以重新再使用
if(stick[i]==nLeft||nLeft==L) return 0;//下一次的递归深入中，刚建了一个新棍，结果后面没有符合条件的棍，
//返回这一层时stick[i]==nLeft，而这一层也要返回
} //或者这一层刚开了一个新的棍，但剩余棍中没有符合的棍即nLeft==L,这也需要返回上层
return 0;
}
int main()
{
int i,totalLength;
while(scanf("%d",&N),N){
for(totalLength=i=0;i<N;++i){
scanf("%d",&stick[i]);
totalLength+=stick[i];
}
sort(stick,stick+N,cmp);//一次剪枝
for(L=stick[0];L<=(totalLength>>1);++L)
if(totalLength%L==0){ //二次剪枝
memset(anUsed,0,sizeof(anUsed));
if(DFS(N,L)) break;
}
if(L>(totalLength>>1)) printf("%d\n",totalLength);//三次剪枝
else printf("%d\n",L);
}
return 0;
}