题目描述

blablabla

样例

blablabla

算法1

(dfs搜索+剪枝) $$

很明显本题是一个搜索题，难点在于优化和剪枝。
1、样例中会有大于50的数字，根据题意，我们直接忽略就好。
2、由于是求最小可能长度，所以我们只要从小到大枚举原始长度，依次检验能否拼成，然后输出第一个成功的就ok。原始长度的最小值显然是小木棍的最大值，这时这些小木棍直接自己拼成一个原始木棍。最大值是总长度的一半，也就是正好拼成两个长度相等的大木棒。如果这些都不满足，那就只能是所有小木棍合成一个了。枚举的时候也不用每个都去检验，很明显只有原始长度是总长度约数的情况下才可能满足条件。
3、我们在拼接每个原始木棍时，先选最大的木棍，再选小一点的木棍来补足长度，这样显然成功率更高。所以我们读入木棍长度后做一个排序，把长的木棍放前边，搜索的时候从前往后去找。
4、现在开始做搜索中的优化，使用dfs(int k,int rest,int last),k是现在正在拼的原始木棍的编号，rest是当前还剩多少长度没拼，last是上一个拼进去的小木棍的下标。搜索时我们从last+1开始找，往后找到第一个能塞到现在这个木棍里的小木棍，也就是第一个满足a[i]<=rest的。因为数组a是单调的，用一个二分就能找到满足要求的i。
5、当我们在搜索中成功拼完所有小木棍后直接把success置true，层层退出dfs，如果执行完某个dfs后success是false，就说明这次尝试是失败的，继续尝试其他情况。
6、当我们选中了某个小木棍调用dfs函数后，如果失败。继续进行尝试时直接跳过与这一根小木棍长度相同的木棍，因为情况完全相同，肯定也是失败。我们提前做预处理，nx[i]中存储和i木棍长度相等的最后一根木棍。再选择的时候直接从第nx[i]+1根，也就是比当前更小的木棍开始尝试。
7、调用dfs函数结果失败时，如果当前选择的小木棒的长度刚好等于rest长度，也就是选择这根木棒刚好拼出一根初始木棒，说明这种选择已经是最好的选择了，这样都能失败，在选择其他的肯定也失败，所以已经没必要继续选择别的木棒尝试，而是直接退出这一层函数，重新选择上一根木棒。

时间复杂度

参考文献

C++ 代码

#include<bits/stdc++.h>
using namespace std;
int n,cnt,sum,len,m;
int a[70],nx[70];
bool st[70];
bool success;
bool cmp(int a,int b){return a>b;}
void dfs(int k,int rest,int last){
    int i;
    if(!rest){
        if(k==m){success=true;return;}      //优化5
        for(i=1;i<=cnt;i++)if(!st[i])break; //开始拼一根新木棍时直接选最长的
        st[i]=true;
        dfs(k+1,len-a[i],i);
        st[i]=false;
        if(success)return;                  //优化5
    }
    int l=last+1,r=cnt,mid;                 //优化4
    while(l<r){
        mid=(l+r)/2;
        if(a[mid]<=rest)r=mid;
        else l=mid+1;
    }
    for(i=l;i<=cnt;i++){
        if(st[i])continue;
        st[i]=true;
        dfs(k,rest-a[i],i);
        st[i]=false;
        if(success)return;
        if(rest==a[i])return;               //优化7
        i=nx[i];                            //优化6
    }
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        if(x>50)continue;
        a[++cnt]=x;
        sum+=x;
    }
    sort(a+1,a+1+cnt,cmp);
    nx[cnt]=cnt;
    for(int i=cnt-1;i>0;i--)           //预处理nx
        if(a[i]==a[i+1])nx[i]=nx[i+1];
        else nx[i]=i;
    for(len=a[1];len<=sum/2;len++){
        if(sum%len!=0)continue;        //优化2 
        m=sum/len;
        success=false;
        st[1]=true;
        dfs(1,len-a[1],1);
        st[1]=false;
        if(success){cout<<len;return 0;}
    }
    cout<<sum;
    return 0;
}