题目链接:传送门

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;
}