小木棍

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 1375 字
枚举原木棍长度，DFS 拼接配多重剪枝
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1442
// 题意：一堆等长木棍被砍成 n 段（每段不超过 50），求原始木棍的最小可能长度。
// 思路：枚举原始长度 len（必须是总长的约数且不小于最长段），用 DFS 拼木棍。
// 1. 木棍长度从大到小排序，长的先放，分支更少。
// 2. 拼当前木棍时只往后找，避免枚举同一组合的不同排列。
// 3. 关键剪枝：某段作为一根新木棍的第一段放不进去就整体失败；刚好拼满一根却失败也直接回溯。
// 复杂度：指数级搜索，靠剪枝在 n <= 60 时很快出解
// 易错点：len 从最长段开始枚举并且必须是总长的约数，漏掉这个条件会做大量无用枚举。
// 易错点：同一层搜索中相同长度的木棍只尝试一次，否则会重复搜索完全等价的分支导致超时。
#include <bits/stdc++.h>
using namespace std;
int n, len, need;
vector<int> a;
vector<int> used;
bool dfs(int done, int cur, int start){
    if(done == need) return true;
    if(cur == len) return dfs(done + 1, 0, 0);
    int prev = -1;
    for(int i = start; i < n; i++){
        if(used[i] || a[i] == prev) continue;
        if(cur + a[i] > len) continue;
        used[i] = 1;
        if(dfs(done, cur + a[i], i + 1)) return true;
        used[i] = 0;
        prev = a[i];
        if(cur == 0) return false;
        if(cur + a[i] == len) return false;
    }
    return false;
}
int main(){
    if(!(cin >> n)) return 0;
    a.resize(n);
    int sum = 0, mx = 0;
    for(int i = 0; i < n; i++){
        cin >> a[i];
        sum += a[i];
        mx = max(mx, a[i]);
    }
    sort(a.begin(), a.end(), greater<int>());
    used.assign(n, 0);
    for(len = mx; len <= sum; len++){
        if(sum % len) continue;
        need = sum / len;
        if(dfs(0, 0, 0)) break;
    }
    cout << len << "\n";
    return 0;
}
小木棍

正文

一本通·提高篇的其它内容
