Sticks
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 4755 Accepted Submission(s): 1318
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.
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.
file contains zero.
Output
The output file 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 0
Sample Output
6 5
Code:
剪枝优化无非就是通过写代码前正确的判断去掉不可能出现的子树来减少运行时间, 当然需要正确并且准确的推断
在本题中:
把计算sum的约数的范围缩小至a[max]到sum/2,
相同的输入数据可以只判断第一个,节约时间
#include"stdio.h"
#include"iostream"
#include"algorithm"
#include"string.h"
using namespace std;
int a[70],sign[70],n,sum;
int cmp(int a,int b)
{
if(a>b) return true;
return false;
}
int dfs(int shao,int p,int i,int num)//当前木棍需要补足的长度,p是元素的下标
{ // i是尝试着的每个木棍的长度,num是第几个木棍
int j;
if(num*i==sum) return 1;
bool flag;
for(j=p+1;j<=n;j++)
if(!sign[j] && shao>=a[j])//这根木棍与当前标准长度相差的长度short, 找到一个数可以让short减掉
{
sign[j]=1;
if(shao==a[j]) flag = dfs(i,0,i,num+1);//如果正好可以减为0,则进行下一根木棍的拼接
else flag = dfs(shao-a[j],j,i,num);//否则就继续寻找下一个可以减掉的长度
sign[j]=0;
if(p==0) return flag;
else if(flag) return flag;
while(a[j]==a[j+1]) j++;//相同的直接跳过
}
return 0;
}
int main()
{
int i;
while(scanf("%d",&n),n)
{
sum=0;
for(i=1;i<=n;i++)//不知道为什么非要从1开始存
{
scanf("%d",&a[i]);
sum += a[i];
}
sort(a+1,a+n+1,cmp);
memset(sign,0,sizeof(sign));
int ans=sum;
for(i=a[1];i<=sum/2;i++)//从最长的木棍依次往后
if(sum%i==0 && dfs(i,0,i,0)) {ans = i;break;}
printf("%d\n",ans);
}
return 0;
}
/*
64
40 40 30 35 35 26 15 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 40 43 42 42 41 10 4 40 40 40 40 40 40 40 40 40 40 40 40 40 40 25 39 46 40 10 4 40 40 37 18 17 16 15 40 40 40 40 40 40 40 40
9
15 3 2 11 4 1 8 8 8
*/