UVa 307 【小木棍 Sticks】题解

这道题总体来说还是非常简单的，就是搜索+剪枝。

搜索怎么搜应该没什么好讲的。

以下为几个剪枝思路：

1. 枚举原始木棒的长度时，最小值显然应该为所有小木棍的最大值。最大值显然应该是所有木棍的长度总和，但我们并不需要这么做。我们只需要枚举到所有木棍的长度总和的二分之一，加入这样都没有解决方案，那么答案就显然是所有木棍的长度的总和。


2. 对于长度大于50的木棍直接忽略（不符合要求）


3. 将所有输入的木棍按长度从大到小排序（这个可以感性理解）


4. 每次DFS时，如果当前长度进行搜索时不行，那么可以直接跳过和他长度相等的木棒（因为在当前状态不变的情况下liu）


5. 若当前木棒的长度等于当前在拼的木棒的剩余长度且情况不可行时，那么直接回溯（因为加入继续搜下去也不过是用后面的几根木棒组成了当前木棒的长度，浪费了更多资源，留给后面的选择也更少了，显然不是最优解）。


6. 若当前在拼的木棒长度等于期望的原始长度，那么直接回溯（类似于上米娜两种情况，继续搜下去不仅状态不会改变，反而状态变少了，显然不是最优解）。

有了以上这么多的剪枝的支持，这道题就完成了。

下面给出完整代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int nn, n, cnt, ma, mi, ans, num, a[70], use[70], pan;
inline void dfs(int sum, int k, int last)
{
    if (sum == ans)
    {
        cout << num << endl;//因为搜索的顺序是从小到大的，所以第一个搜到的必定是最小的
        pan = 1;
        return;
    }
    if (k == 0)
    {
        dfs(sum + 1, num, 0);
        return;
    }
    if (k < mi)
        return;
    for (register int i = last + 1; i <= n; ++i)
    {
        if (use[i] == 0 && k >= a[i])
        {
            use[i] = 1;
            dfs(sum, k - a[i], i);
            use[i] = 0;
            if (pan == 1)
                return;
            while (a[i + 1] == a[i])
                ++i;
            if (k == num || k == a[i])
                return;
        }
    }
    return;
}
bool cmp(int aa, int bb)
{
    return aa > bb;
}
int main()
{
    while (cin >> nn)
    {
        if (nn == 0)
            return 0;
        pan = 0;
        n = 0;
        cnt = 0;
        ma = 0;
        mi = 0x3f3f3f;
        ans = 0;
        num = 0;
        memset(use, 0, sizeof(use));
        for (register int i = 1; i <= nn; ++i)
        {
            int lin;
            cin >> lin;
            if (lin <= 50)
            {
                a[++n] = lin;
                cnt += a[n];
                ma = max(ma, a[n]);
                mi = min(mi, a[n]);
            }
        }
        sort(a + 1, a + n + 1, cmp);
        for (register int j = ma; j <= cnt / 2; ++j)
            if (cnt % j == 0)
            {
                num = j;
                ans = cnt / j;
                dfs(0, num, 0);
                if (pan == 1)
                    break;
            }
        if (pan == 0)
            cout << cnt << endl;
    }
    return 0;
}