「Luogu1120」小木棍 - 搜索

题目链接:传送门

Description

乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过50。 现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。 给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。

Input

输入文件共有二行。 第一行为一个单独的整数N表示砍过以后的小木棍的总数,其中N≤65 (管理员注:要把超过50的长度自觉过滤掉,坑了很多人了!) 第二行为N个用空个隔开的正整数,表示N根小木棍的长度。

Output

输出文件仅一行,表示要求的原始木棍的最小可能长度

Solution

这题其实就是dfs+剪枝。 dfs(now,len,x,deep,times)表示当前要拼的木棍剩余now,总长为len,用到第x根木棍,之前已经拼成了deep跟木棍,总共要拼times根木棍,直接爆搜即可 剪枝: 1、先将所有棍子按照长度从大到小排序,方便剪枝 2、如果使用当前木棍之后无法拼好,且该木棍正好能补全要当前要拼成的木棍,剪枝 3、如果now=len,也就是说now是新一组木棍的开始,但用了剩下木棍中最大的木棍都拼不了,剪枝 4、若当前长度的木棍拼不成,那么和它一样长的木棍也会拼不成,剪枝 大概就是这么几个剪枝,然后就可以A了

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include<bits/stdc++.h>
using namespace std;
const int maxn=70;
int n;
int a[maxn],p[maxn];
inline int cmp(int x,int y){
return x>y;
}
inline int dfs(int now,int len,int x,int deep,int times){
if(times==deep){
return 1;
}
if(now==0){if(dfs(len,len,1,deep+1,times))return 1;}
for(int i=x;i<=n;i++){
if(!p[i] && a[i]<=now){
p[i]=1;
if(dfs(now-a[i],len,x+1,deep,times))return 1;
p[i]=0;
if(a[i]==now || now==len)break;
while(a[i+1]==a[i])i++;
}
}
return 0;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
scanf("%d",&n);
int sum=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
if(a[i]>50)i--,n--;
else sum+=a[i];
}
sort(a+1,a+n+1,cmp);
int ans;
for(int i=a[1];i<=sum;i++)
if(!(sum%i)){
int tot=sum/i;
if(dfs(i,i,1,0,tot)){ans=i;break;}
}
cout<<ans<<endl;
return 0;
}
感谢你的赞赏!