题目描述

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过50个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

输入格式
输入包含多组数据，每组数据包括两行。

第一行是一个不超过64的整数，表示砍断之后共有多少节木棍。

第二行是截断以后，所得到的各节木棍的长度。

在最后一组数据之后，是一个零。

输出格式
为每组数据，分别输出原始木棒的可能最小长度，每组数据占一行。

数据范围
数据保证每一节木棍的长度均不大于50。

样例

输入样例：
9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0
输出样例：
6
5

深搜+剪枝

首先确定每一根要接多长再一根一根的搜索，接好一根再接下一根

剪枝：
1.如果当前木棍已经使用过
2.如果当前木棍接在当前木棒上超出限制
3.在每一根木棒内部，如果（1,3）可以，那么（3,1）也是可以的，防止重复，设置start变量
4.如果失败且回溯到第一根木棍
5.如果失败且回溯到最后一根木棍

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=70;

int n,sum,length;//n是有几根木棍，sum是所有木棍总长，length是每根木棒多长
int sticks[N];//每一根木棍的长度
bool st[N];//每一根木棍用过没有

bool dfs(int u,int cur,int start){//u是已经拼好了几根木棒，cur是当前这根在拼的木棒已经拼了多长，start是从第几根木棍开始拼
    if(u*length==sum) return true;//如果拼好了就返回true
    if(cur==length)    return dfs(u+1,0,0);//如果这一根拼好了就进行下一根
    for(int i=start;i<n;i++){
        if(st[i])    continue;//如果这根木棍已经用过，就继续循环
        int l=sticks[i];
        if(cur+l>length)    continue;//如果这根木棍接上会超，就继续循环
        st[i]=true;
        if(dfs(u,cur+l,i+1))  return true;//再从下一根木棍开始拼，成功就可以提前返回了
        st[i]=false;//回溯

        if(!cur) return false;
        if(cur+l==length)  return false;
        int j=i;
        while(j<n&&sticks[j]==l)  j++;
        i=j-1;
    }
    return false;//如果在前面都还没有返回，就没有拼成功
}
int main(){
    while(cin>>n,n){
        sum=0;length=0;
        memset(st,false,sizeof(st));
        for(int i=0;i<n;i++){
            cin>>sticks[i];
            if(sticks[i]>50)  continue;
            sum+=sticks[i];
            length=max(length,sticks[i]);//找到最长的木棍，拼起来的木棒长度最小也要这么长
        }

        sort(sticks,sticks+n);
        reverse(sticks,sticks+n);
        for(int i=0;i<n;i++){
            if(sticks[i]>50)
                st[i]=true;//这一步一定要放在排序的后面，否则排序后原本是>50的位置排序后已经变化了
        }
        while(true){
            if(sum%length==0&&dfs(0,0,0)){
                cout<<length<<endl;
                break;
            }
            length++;
        }
    }
    return 0;
}