关键字：剪枝。
Link&Limit
时间限制：1000ms 空间限制：131072kb
Description
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
Input Format
第一行为一个单独的整数N表示看过以后的小木柜的总数，其中N≤60
（管理员注：要把超过50的长度自觉过滤掉，坑了很多人了！）
第二行为N个用空个隔开的正整数，表示N根小木棍的长度。
Output Format
仅一行，表示要求的原始木棍的最小可能长度。
Sample Input #1
9
5 2 1 5 2 1 5 2 1
Sample Output #1
6
搜索题。设所有木棍长度和为sum，首先枚举原木棍可能的长度ans（sum mod ans = 0），之后一一将小木棍尝试填入以凑出ans的长度。当然，我们需要一些剪枝：
1、将小木棍按长度从大到小排序。因为先放长木棍可以更快地缩小待填长度，从而更快搜索出答案。
2、由于每根木棍都必须填入，所以凑出新木棍的第一根小木棍必须是可用小木棍中最长的。这种在搜索树深度不大时进行的剪枝是非常强力的。
3、如果存在一根木棍，只要填入它就能凑齐一个ans的长度，我们就要优先考虑这根木棍（用很多根小木棍凑齐同样长度一般不优，因为小木棍更加灵活，其它地方可能更有用）。
4、枚举木棍时，如果接下来所有木棍都用上还凑不齐ans，此时的枚举一定是不合理的。
本题的4个剪枝其实也是许多搜索题中的通用剪枝，练习时还应多多考虑。
#include <stdio.h>
#include <stdlib.h>
int n,m = 0,ans,tot,l[65],cnt[55],pre[65];
short ok = 0;
int comp(const void *a, const void *b)
{
return *(int*)b - *(int*)a;
}
void dfs(int dep,int sum,int sta)
{
int i;
if(dep>tot) { ok = 1; return;}
for(i=sta;i<=n;i++)
{
if(sum+pre[n]-pre[i-1]<ans) break;
if(!cnt[l[i]] || sum+l[i]>ans) continue;
cnt[l[i]]--;
if(sum+l[i] == ans) dfs(dep+1,0,m+1);
else
{
if(ans-sum-l[i]<=50 && cnt[ans-sum-l[i]])
{
cnt[ans-sum-l[i]]--;
dfs(dep+1,0,m+1);
cnt[ans-sum-l[i]]++;
}
else dfs(dep,sum+l[i],i+1);
}
cnt[l[i]]++;
if(ok||!sum) return;
}
}
int main()
{
int i,sum = 0;
scanf("%d",&n);
for(i=1;i<=n;i++)
{
scanf("%d",&l[i]);
if(l[i]>50) m++;
else { sum += l[i]; cnt[l[i]]++;}
}
qsort(l+1,n,sizeof(int),comp);
for(i=1;i<=n;i++) pre[i] = pre[i-1] + l[i];
for(ans=l[m+1];ans<=sum;ans++)
{
if(sum%ans) continue;
tot = sum/ans;
dfs(1,0,m+1);
if(ok) break;
}
printf("%d",ans);
return 0;
}
评论 (0)
