题解 | #小木棍#

思路： 要求最短的原长，直接从最长的小木棍枚举到全部小木棍和sum，然后用dfs去看每个枚举的长度是否可行即可，但此处还需要去剪枝： 1、枚举的长度要满足可以被总长sum整除； 2、当一个小木棍放在第一个位置的时候不能满足条件，那么这个时候的枚举长度是不可取的，因为第一个位置是最宽松的，此时不行那么以后都不可能；同理当一个木棍放在最后一个位置满足本身大木棍但无法满足后续大木棍时也不可取； 3、当前小木棍不能满足，那么其他与他一样长的木棍也不能满足，直接跳过；

代码：

#include<bits/stdc++.h>
#include<algorithm>
using namespace std;
int n;
int a[100];//记录小木棍长度
int v[100];//标记对应编号小木棍是否用过；
bool cmp(int x,int y)
{
    return x>y;
}
//开始搜索
bool dfs(int num,int l,int res,int now)//num是剩余木棍数目，l是枚举长度，res是每次大木棍剩余长度，now是当前小木棍编号
{
    if(res==0&&num==0)return 1;//木棍用完且刚好满足枚举长度直接返回true
    if(res==0)res=l,now=0;//木棍还没有用完，填充下一个大木棍
    for(int i=now;i<n;i++)
    {
        if(v[i])continue;//是否用过
        if(a[i]>res)continue;//是否超过了剩余的长度
        v[i]=1;
        if(dfs(num-1,l,res-a[i],i))return 1;
        v[i]=0;
        if(res==l||res==a[i])return 0;//对应剪枝2
        while(a[i]==a[i+1])i++;//对应剪枝3
    }
    return 0;
}
int main()
{
    cin>>n;
    int sum=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        sum+=a[i];
    }
    sort(a,a+n,cmp);//从大到小排序
    int i;
    for(i=a[0];i<=sum;i++)
    {
        if(sum % i != 0) continue;//对应剪枝3
        if(dfs(n, i, i, 0)) break;
    }
    cout<<i;
    return 0;
}