此题请注意:如果你发现你的算法无比的优秀,没有任何错误,但是死活就是不能对,WA的一次又一次,那么温馨提示您:请自动忽略大于50的数据,没错这就是一个数据出题人的锅.而且还就是不说出来.

题目描述

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

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

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

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

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

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

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

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

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

样例

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

搜索+剪枝

下面为剪枝细目表

1. 优化搜索序列:优先选择较长的木棍
2. 排除等效冗余:要求先后加入的木棍有单调性,因为先来一根长度为x的木棍,再来一个长度为y的木棍,其实他们反过来是一样的,既然如此当然要有单调性.
3. 排除等效冗余:对于当前木棍,记录最近一次尝试拼接失败的木棍,因为它失败了,那么肯定之后不能尝试再次凭借和他长度一模一样的木棍.因为他们是一模一样,没有任何差别,那么A死了,后面的A自然也得死,虽然他们下标不一样.
4. 排除等效冗余:如果第一次尝试拼入木棍就失败的话,那么这个分治必然也是失败的,因为在拼入这些木棍前,面对的原始木棍都是还没有拼接的,他们都是等效的.

C++ 代码

#include <bits/stdc++.h>
using namespace std;
const int N=100;
int a[N],n,m,max_val,sum,i,len,cnt,vis[N],true_n;
int cmp(int a,int b)//从大到小排序
{
    return a>b;
}
int dfs(int cnm,int cab,int last)//cnm为当前第几段了,cab记录当前段的长度,last为上一次已经选过的值
{
    if (cnm>cnt)//满足条件了
        return true;
    if (cab==len)//如果发现这一段已经用完了,下一段接着来.
        return dfs(cnm+1,0,1);
    int fail=0;//记录上一次失败的值,如果这次还是的话,那么肯定是不能选择的
    for(int i=last;i<=true_n;i++)
        if (!vis[i] && a[i]!=fail && cab+a[i]<=len)//没有被访问,不是上一次失败的值,长度满足在len以内
        {
            vis[i]=1;
            if (dfs(cnm,cab+a[i],i+1))//开始下一次dfs
                return true;
            fail=a[i];//失败了,当然要记录了
            vis[i]=0;//这个数没有选择
            if (cab==0 || cab+a[i]==len)//如果cab为0,或者相加正好是len,但是失败了,那么一定是失败了.
                return false;
        }
    return false;//所有的都失败了,那么肯定是失败的.
}
int main()
{
    ios::sync_with_stdio(false);
    while(cin>>n && n)
    {
        int x;
        max_val=0,sum=0;true_n=0;
        for(i=1;i<=n;i++)
        {
            cin>>x;
            if (x>50)//自动忽略掉
                continue;
            true_n++;//这才是真正的n QAQ
            a[true_n]=x;
            max_val=max(max_val,a[true_n]);
            sum+=a[true_n];
        }
        sort(a+1,a+1+true_n,cmp);//排序优化搜索顺序
        for(len=max_val;len<=sum;len++)//优化
        {
            if (sum%len)//如果除不尽,肯定不满足题意
                continue;
            cnt=sum/len;//计算出cnt多少段
            memset(vis,0,sizeof(vis));//初始化
            if (dfs(1,0,1))//搜索成功,最小值就是它
                break;
        }
        cout<<len<<endl;
    }
    return 0;
}