传送门

玄关

不知道少了哪个剪枝

/*
Luogu P1120 小木棍
https://www.luogu.com.cn/problem/P1120
*/
#include "iostream"
#include "algorithm"
using namespace std;
int a[70], nxt[70], n, m, high, low=0;
bool possible, vis[70];
void dfs(int x, int target, int pre, int cnt){
    if(x==target){
        cnt++;
        if(cnt==m-1) possible=true;
        else dfs(0, target, 0, cnt);
        return;
    }
    int l=pre+1, r=n, mid, y=target-x;
    while(l<r){
        mid=(l+r)>>1;
        if(a[mid]<=y) r=mid;
        else l=mid+1;
    }
    for(int i=l;i<=n;i++){
        if(vis[i]) continue;
        vis[i]=true;
        if(x+a[i]<=target) dfs(x+a[i], target, i, cnt);
        if(possible) return;
        vis[i]=false;
        if(y==a[i] || y==x) return;
        i=nxt[i]-1;
    }
}
bool cmp(int i1, int i2){
    return i1>i2;
}
int main(){
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
        if(a[i]>low) low=a[i];
        high+=a[i];
    }
    sort(a+1, a+1+n, cmp);
    nxt[n]=n+1;
    for(int i=n-1;i>=1;i--){
        if(a[i]==a[i+1]) nxt[i]=nxt[i+1];
        else nxt[i]=i+1;
    }
    for(int i=low;i<=high/2;i++){
        if(a[n]<=i && !(high%i)){
            possible=false;
            m=high/i;
            dfs(0, i, 0, 0);
            if(possible){
                cout << i;
                return 0;
            }
        }
    }
    cout << high;
}