POJ1011:Sticks 题解 & 剪枝典例

剪枝技巧

这道题的剪枝技巧非常的精巧，有很多的技巧可以在做题中良好的运用。我先把代码贴出，然后我们再来分析。

// POJ1011.cpp
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn = 70;
int n, arr[maxn], stcnt, len;
bool vis[maxn];
bool cmp(int a, int b) { return a > b; }
bool dfs(int st, int cab, int last)
{
    if (st > stcnt)
        return true;
    if (cab == len)
        return dfs(st + 1, 0, 1);
    int fail = 0;
    for (int i = last; i <= n; i++)
        if (fail != arr[i] && cab + arr[i] <= len && !vis[i])
        {
            vis[i] = true;
            if (dfs(st, cab + arr[i], i + 1))
                return true;
            fail = arr[i];
            vis[i] = false;
            if (cab == 0 || cab + arr[i] == len)
                return false;
        }
    return false;
}
int main()
{
    while (scanf("%d", &n) && n)
    {
        int mx_val = 0, sum = 0;
        for (int i = 1; i <= n; i++)
            scanf("%d", &arr[i]), mx_val = max(mx_val, arr[i]), sum += arr[i];
        sort(arr + 1, arr + n + 1, cmp);
        for (len = mx_val; len <= sum; len++)
        {
            if (sum % len)
                continue;
            stcnt = sum / len;
            memset(vis, false, sizeof(vis));
            if (dfs(1, 0, 1))
                break;
        }
        printf("%d\n", len);
    }
    return 0;
}

先来简要的说明一下 DFS 的过程。DFS 中有三个参数，其中参数\(st\)代表目前已完全合成的棍子数，\(cab\)代表当前棍子合成出来的长度，\(last\)代表上一次合成用到的最后一根棍子的编号。我们会预先把整个棍子的数量从大到小排序，然后每次 DFS 的遍历就从\(last\)变量开始，这是一个地方的剪枝；其中还有另一个地方，就是如果我们在后续的 DFS 中找到了答案，那么我们整个搜索就可以停止了：我们来看主函数，长度的枚举是从小到大的，所以一定是最优解。用\(fail\)变量来减去重复长度的杂枝。如果在后续的遍历中都没有得到符合的情况，且这根棍子的长度为\(0\)或者为\(len\)，意味着无论如何都无法合成了，故直接返回\(false\)。这就是这道题的剪枝技巧。

我们发现在搜索中，我们可以采用排序、搜索顺序优化、剪除重复搜索的方式来大幅度的提高我们程序的运行速度。剪枝是非常重要的一个环节。