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\)。这就是这道题的剪枝技巧。

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

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注