[数据结构与算法]洛谷 小木棍（暴力+剪剪剪剪枝）

题目链接：

小木棍 - 洛谷

思路：

如果只考虑暴力，做法很简单，枚举所有可能的最终长度，都跑一遍dfs，取最小结果即可，本题难就难在大量的剪枝，具体见代码。

我的思路也是参考了大佬的博客：题解 P1120 【小木棍 ［数据加强版］】 - Kaori 的博客 - 洛谷博客

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 70;
int n, x, sum=0;
int m, len; //要拼的木棍数量，长度
int a[maxn], cnt;
bool used[maxn];
bool ok = false; //当前是否拼接成功
bool cmp(int i,int j) {return i>j;}
void dfs(int cur, int last, int rest){ //当前拼的数量，最后用的木棍编号，剩下要拼的长度
    if(rest==0){
        if(cur==m) {ok=1; return;}
        int i;
        for(i=1; i<=cnt; i++)
            if(!used[i]) break;
        used[i] = 1;
        dfs(cur+1, i, len-a[i]);
        used[i] = 0;
        if(ok) return; //如果成功，直接返回
    }
    //二分查找第一个长度不大于rest的木棍
    int left = last+1, right = cnt, mid;
    while(left < right){
        mid = (left+right)>>1;
        if(a[mid]<=rest) right = mid;
        else left = mid+1;
    }
    //注意从left开始，这点很重要（从长到短逐个选择，保证顺序和灵活性）
    for(int i=left; i<=cnt; i++){
        if(used[i] || a[i]>rest) continue; //用过的或者太长的不能用
        if(!used[i-1]&&a[i]==a[i-1]) continue; //和前面等长，前面不能过，这个也不能
        used[i] = 1;
        dfs(cur,i,rest-a[i]);
        used[i] = 0;
        if(ok) return; //如果成功，直接返回

        if(rest==a[i] || rest==len) return; //特殊优化
    }
}
int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    cin >> n;
    for(int i=1; i<=n; i++){
        cin>>x;
        if(x<=50) {a[++cnt] = x; sum += x;}
    }
    sort(a+1,a+n+1,cmp); //排序优化，短木棍更加灵活，排在后面，取的时候先拿长的再拿短地
    for(len=a[1]; len<=sum/2; len++){
        if(sum%len != 0) continue; //不是整倍数，必定合不出来
        m = sum/len; //要拼的木棍数量
        ok = 0; 
        used[1] = 1;
        dfs(1,1,len-a[1]);
        used[1] = 0;
        if(ok) {cout<<len; return 0;}
    }
    cout<<sum;
}