【洛谷 P1120】小木棍——搜索剪枝

P1120 小木棍 - 洛谷

題目描述

喬治有 \(n\) 根同樣長的小木棍，他把這些木棍隨意砍成幾段，直到每段的長都不超過 \(50\)，現在他想把小木棍拼接成原來的樣子，但是卻忘記了自己開始時有多少根木棍和它們的長度，給出每段小木棍的長度 \(a_i\)，幫他找出原始木棍的最小可能長度，

資料范圍

\(1 \leq n \leq 65\)，\(1 \leq a_i \leq 50\)，

時空限制

260ms，128MB，

題意理解

給定一個多重數集，將其劃分為若干子集，保證存在至少一種劃分方式使得各子集中元素之和相等，求上述和的最小值，

演算法分析

暴力演算法

根據題意和資料范圍，考慮迭代原始木棍長度，每次進行 最暴力 的 DFS 直到找到一種可行方案，時間復雜度為 \(O(nm \cdot n!)\)，

優化一

顯然，當原始木棍比已知最長木棍短時，不可能有解，故直接從已知最長木棍的長度開始迭代，

優化二

顯然，當原始木棍長度不能被木棍總長度整除時，不可能有解，直接跳過，

優化三

因為每次搜索的目的是證明解的存在性，所以只要找到一組解就可以停止搜索，

利用暴力演算法結合以上三種最簡單的優化，可以通過本題 30 組資料中的 9 組，

優化四

注意到在拼湊每一根原始木棍時，如果每次選取都嘗試所有未使用的木棍會造成大量重復搜索，故改為只嘗試比上一次選取更靠后的木棍，

優化五

注意到已知木棍中出現較多長度相等者的情況，此時會造成大量重復搜索，故考慮在搜索之前對所有已知木棍進行 \(O(n)\) 的預處理操作，將同樣長度的木棍合并，

優化六

注意到搜索順序對搜索樹的影響，相比于從更短的已知木棍開始搜索，從更長者開始的情況更少而且更易于剪枝，故改用此順序，

至此，可以通過本題 30 組資料中的 19 組，

優化七

在上述優化的基礎上，注意到選取已知木棍時的單調性，為減小常數可以二分找到第一個不超過剩余長度的已知木棍長度，

優化八

在優化一和優化二的基礎上，注意到并非所有滿足這兩個條件的數都能由若干個已知木棍長度相加得出，故考慮利用 01 背包進行優化，

優化九

注意到在拼湊每一根原始木棍時，如果有解則當前最長的已知木棍必被使用，否則會造成重復搜索，故對此情況特判，

至此，可以通過本題 30 組資料中的 26 組，

優化十（重點）

注意到如果當前已知木棍長度正好等于拼湊成原始木棍所剩的長度，此時該木棍可以等價于更短的已知木棍拼湊出的長度和相同的組合，若此時無解，則使用更短者也不可能有解，故不再繼續嘗試，

至此，可以通過本題全部資料，

實作代碼

#include <bits/stdc++.h>

using std::cin;
using std::cout;
constexpr int MAXN = 70;
int n, m, sum, now;
// m: 合并后長度的種數（優化五）
// sum: 所有長度之和
// now：當前搜索的原始長度
bool ok;  // 是否找到解
int a[MAXN];
int temp[MAXN];         // 用于線性預處理（優化五）
int dict[MAXN];         // 記錄序號對應的原始值（優化五）
int pool[MAXN];         // 記錄序號對應的值的出現次數用于回溯（優化五）
bool vis[MAXN * MAXN];  // 用于 01 背包（優化八）

void dfs(int cnt, int add, int last) {
    // cnt: 已經成功的組數
    // add: 當前組已有的和
    // last: 上一次選取的值（優化四）
    if (ok)
        return;  // 優化三
    if (add == now)
        ++cnt, add = 0, last = m;
    if (cnt * now == sum) {
        ok = true;
        return;
    }
    int l = 1, r = last;
    int mid;
    while (l <= r) {
        mid = (l + r) >> 1;  // 優化七
        if (add + dict[mid] <= now)
            last = mid, l = mid + 1;
        else
            r = mid - 1;
    }
    for (int i = last; i >= 1; --i) {  // 優化四和優化六
        if (pool[i] == 0)
            continue;
        if (add + dict[i] > now)
            continue;
        --pool[i];
        dfs(cnt, add + dict[i], i);
        ++pool[i];
        if (add + dict[i] == now || add == 0)  // 優化九和優化十
            return;
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    int maxv = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        sum += a[i];
        ++temp[a[i]];  // 優化五
        maxv = std::max(maxv, a[i]);
    }
    vis[0] = true;
    for (int i = 0; i <= n; ++i)
        for (int j = sum - a[i]; j >= 0; --j)
            if (vis[j])
                vis[j + a[i]] = true;  // 優化八
    for (int i = 1; i <= maxv; ++i)
        if (temp[i] > 0) {
            ++m;
            dict[m] = i;
            pool[m] = temp[i];  // 優化五
        }
    for (now = maxv; now <= sum; ++now) {  // 優化一
        if (sum % now != 0 || !vis[now])
            continue;  // 優化二
        ok = false;
        dfs(0, 0, m);
        if (ok)
            break;
    }
    cout << now << '\n';
    return 0;
}

部分思路來自 muduzx62 的視頻 和 Kaori 的題解，在此表達感謝，
轉載請注明出處，原文地址：https://www.cnblogs.com/na-sr/p/luogu-stick.html

標籤：其他

上一篇：C++基礎-6-繼承

下一篇：機器學習-習題(一)