现在有n根木棍,然后需要把它们拼成同样长度的木棍,问满足这个条件的最短的长度是多少?
搜索一下,显然长度之和应该能整除木棍数量,用这个数去看木棍能不能达成
有几个剪枝,先用桶排序,然后每次算的时候从大向小装,记一下装到的长度l,如果没有拼好这个木棍就接着l开始,如果拼好了就开始新的木棍从最大的那个长度开始。(想一想觉得还是很妙的)还有一个神奇的剪枝就是说如果放入了这个木棍,使这个木棍刚好拼好一个完整的棍或者这个木棍使第一个棍,那就不用再往下枚举长度了。因为枚举这个木棍之后的DFS已经把往下枚举的情况考虑过了!
(说的有点啰嗦了
\#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#define inf 0x3f3f3f3f
const int N = 100;
int S[N],sum,max=-inf,flag,min=inf,n,nn;
inline int dfs(int cnt,int now,int sum,int m){
if(flag) return flag;
if(cnt==0){
printf("%d\n",sum);
flag=1;
}
if(now==sum){
dfs(cnt-1,0,sum,max);
}
for(int i=m;i>=min;--i){
if(!S[i]||i+now>sum) continue;
S[i]--;
dfs(cnt,now+i,sum,i);
S[i]++;
if(now==0||now+i==sum) return 0;
}
}
int main (){
while(scanf("%d",&n)&&n){
memset(S,0,sizeof(S));
sum=flag=0;
for(int i=1;i<=n;++i){
int x;
scanf("%d",&x);
if(x<=50){
++nn;
min=std::min(min,x);
max=std::max(max,x);
S[x]++;
sum+=x;
}
}
n=nn;
for(int i=min;i<=sum;++i){
if(sum%i!=0) continue;
dfs(sum/i,0,i,max);
}
}
return 0;
}
0 条评论