链接Miku

代码参考：小蓝书

暴力很好写，可惜过不了，怎么办，剪枝起飞。

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int len[500001];
int fl[500001];
int sum;
int li;
int cnt;
    int maxx=0;
int ans[500001];
bool dfs(int now,int l,int ord){
    if(now>cnt)//over
    return 1;
    if(l==maxx)
    return dfs(now+1,0,1);//开始下一个 
    int fail=0;
    for(int i=ord;i<=n;++i){
        if(!fl[i]&&l+len[i]<=maxx&&fail!=len[i]){//因为是从大到小放的
        //所以说如果不行的话肯定同样长度的都不行 
            fl[i]=1;
            if(dfs(now,l+len[i],i+1))
            return 1; 
            fail=len[i];
            fl[i]=0;
            //不好理解的剪枝
            //l==0的部分是因为如果此木棍出现在新木棍中不可行的话，那么它出现在之后任何一个新木棍的结果都是一样的--不行
            //后半段同理，贪心的考虑一下，一整根木棍都不行的话，就算用几根小木棍拼起来也没有意义 
            if(l==0||l+len[i]==maxx)
            return 0;

        }
    }
    return 0;
}
bool cmp(int x,int y){
    return x>y;
}
int main(){     
        scanf("%d",&n);
        sum=0;
    maxx=0;
    int xiu;
    int lll=0;
        for(int i=1;i<=n;++i){
        scanf("%d",&xiu);
        if(xiu>50)//自动忽略 
        continue;
        len[++lll]=xiu;
        sum+=len[lll];
        maxx=max(maxx,len[lll]);
        }
        n=lll;
        sort(len+1,len+n+1,cmp);
        //从大到小搞啊 
        int i;
        for( ;maxx<=sum;++maxx){
            if(sum%maxx) continue;
            //显然只有原长是总长的因数才有意义 
            cnt=sum/maxx;
            memset(fl,0,sizeof(fl));
            if(dfs(1,0,1)){
            break;
            }
        }
        cout<<maxx<<endl;
    return 0;
}