首页 > 编程学习 > [AcWing 167] 木棒

[AcWing 167] 木棒

发布时间:2022/8/24 0:04:55

image
image

DFS 剪枝


点击查看代码
#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int N = 1e6 + 10;

int n;
int w[N];
int sum, len;
bool st[N];

bool dfs(int u, int s, int start)
{
    if (u * len == sum)
        return true;
    if (s == len)
        return dfs(u + 1, 0, 0);
    // 排除等效冗余 按照组合数枚举
    for (int i = start; i < n; i ++) {
        // 可行性剪枝
        if (st[i] || s + w[i] > len)
            continue;
        st[i] = true;
        if (dfs(u, s + w[i], i + 1))
            return true;
        st[i] = false;
        // 排除等效冗余 放到头尾失败则失败
        if (!s || s + w[i] == len)
            return false;
        // 排除等效冗余 排除掉相同值的元素
        int j = i;
        while (j < n && w[j] == w[i])
                j ++;
        i = j - 1;
    }
    return false;
}

void solve()
{
    while (cin >> n, n) {
        memset(st, false, sizeof st);
        sum = 0;
        for (int i = 0; i < n; i ++) {
            cin >> w[i];
            sum += w[i];
        }
        // 优化搜索顺序 从大到小排序
        sort(w, w + n, greater<int>());
        len = 1;
        while (true) {
            // 可行性剪枝
            if (sum % len == 0 && dfs(0, 0, 0)) {
                cout << len << endl;
                break;
            }
            len ++;
        }
    }
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

  1. 优化搜索顺序
    从大到小排序,减少分支的数量
  2. 可行性剪枝
    只有当单个木棒的长度 \(len\) 可以整除总长度 \(sum\) 时,才进行 \(DFS\)
  3. 排除等效冗余
    ① 按照组合数枚举
    ② 如果当前木棍加到当前棒中失败,则直接略过后面所有长度等于当前木棍的木棍
    ③ 如果当前木棍在当前棒的头部失败,则一定失败
    证明:假设存在一种方案,将当前木棍放到后续的棒中成功,则通过调整法,先将木棍调整到该木棍所在棒的最前面,再交换两木棒的位置,这样就把木棒调整到如果这句话的位置,出现矛盾
    ④ 如果当前木棍在当前棒的尾部失败,则一定失败
    证明:假设存在一种方案,将当前木棍放到后续的棒中成功,由于木棒的长度都相同,那么即使不把当前木棍拼接到当前木棒,最后当前木棒拼接的长度总和还是等于当前木棍,那么通过把这一段的木棍和当前木棍调整,就会出现矛盾
Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号