题目链接 蓝书 167木棒问题（搜索）

我遇到的问题是如果用我这种暴力破解的方法去搜索的话，剪枝的思路应该从哪里开始思考和入手呢，现在有点不太知道接下来怎么考虑

错误的代码：

#include <bits/stdc++.h>


using namespace std;

#define lowbit(S) (S & -S)


#define sz(x) (int((x).size()))
#define pb push_back
#define bg begin()
#define ed end()



//loop
#define each(x, a) for (auto& x : a)



typedef long long int ll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<bool> vb;



const vi dx{-1, 1, 0, 0};
const vi dy{0, 0, -1, 0};
const vi dr{-1, -1, 0, 1, 1, 1, 0, -1};
const vi dc{0, 1, 1, 1, 0, -1, -1, -1};







int ans;
void dfs(const vi& a, vi& capacity, int index, int tot, int k){
    if (ans) return;
    if (index == (int)a.size()){
        for (int i = 0; i < tot; ++i){
            if (capacity[i]) return;
        }
        ans = k;
        return;
    }
    for (int i = 0; i < tot; ++i){
        if (capacity[i] >= a[index]){
            capacity[i] -= a[index];
            dfs(a, capacity, index + 1, tot, k);
            capacity[i] += a[index];
        }
    }
    capacity[tot] -= a[index];
    dfs(a, capacity, index + 1, tot + 1, k);
    capacity[tot] += a[index];
}
int main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n;
    while (cin >> n){
        if (n == 0) break;
        ans = 0;
        vi a(n), capacity(66);
        for (auto& x : a) cin >> x;
        sort(a.bg, a.ed);
        int l = *max_element(a.bg, a.ed);
        while (!ans){
            for (auto& x : capacity) x = l;
            dfs(a, capacity, 0, 0, l);
            l += 1;
        }
        cout << ans << endl;
    }
    return 0;
}

TLE

提问于23天前

__yxc_

416