木棒
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 147207 | Accepted: 34876 |
Description
乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棍的长度都用大于零的整数表示。
Input
输入包含多组数据，每组数据包括两行。第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。第二行是截断以后，所得到的各节木棍的长度。在最后一组数据之后，是一个零。
Output
为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。
Sample Input
9 5 2 1 5 2 1 5 2 1 4 1 2 3 4
Sample Output
6 5
Source
Translator
北京大学程序设计实习, Xie Di
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,sum,cd[65],maxn,len;
bool vis[65];
int cmp(int a,int b)
{
return a>b;
}
bool dfs(int i,int l,int t)
{
if(l==0)
{
t-=len;
if(t==0) return true;
int k=1;
while(vis[k]) k++;
vis[k]=1;
if(dfs(k+1,len-cd[k],t)) return true;
vis[k]=0;
t+=len;
}
else
{
for(int j=i;j<=n;j++)
{
if(j>1&&cd[j]==cd[j-1]&&!vis[j-1]) continue;
if(!vis[j]&&cd[j]<=l)
{
l-=cd[j];
vis[j]=1;
if(dfs(j,l,t)) return true;
l+=cd[j];
vis[j]=0;
}
}
}
return false;
}
int main()
{
while (scanf("%d",&n) != EOF)
{
memset(cd, 0, sizeof(cd));
memset(vis, 0, sizeof(vis));
sum = 0, maxn = 0,len = 0;
if (n == 0)
break;
for(int i=1;i<=n;i++)
{
scanf("%d",&cd[i]);
sum+=cd[i];
maxn=max(maxn,cd[i]);
}
sort(cd+1,cd+n+1,cmp);
bool flag = 0;
for(len=maxn;len<=sum/2;len++)
{
memset(vis,0,sizeof(vis));
if(sum%len==0)
{
if(dfs(1,len,sum))
{
printf("%d\n",len);
flag = 1;
break;
}
}
else continue;
}
if (!flag)
printf("%d\n",sum);
}
return 0;
}