167.木棒

167. 木棒

题目描述：

乔治拿来一组等长的木棒，将它们随机地砍断，使得每一节木棍的长度都不超过 $ 50 $ 个长度单位。

然后他又想把这些木棍恢复到为裁截前的状态，但忘记了初始时有多少木棒以及木棒的初始长度。

请你设计一个程序，帮助乔治计算木棒的可能最小长度。

每一节木棍的长度都用大于零的整数表示。

数据范围：

题解：

注意是等长的木棒，所以很容易想到枚举长度，然后进行搜索。

剪枝策略：

• 枚举的长度需要是总长 sum 的因子

• 首先从大到小排序，然后再选取

  因为这是个组合问题，与选取顺序无关。先选大的，后面的搜索空间变小，比较快。并且保证了单调性。

• 记录最近一次拼接失败的长度，因为该次失败了，所以下一次碰到该长度也不行

• 如果放入第一根木棍失败，那么该方案失败。因为第一次会把所有的情况都搞一遍。

  如果放入最后一根木棒失败，那么该方案失败。可以反证。假设该方案合法，那么最后一根木棒一定可以放进去，出现矛盾，所以该方案不合法。

代码：

using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e2 + 10;
const int maxm = 1e5 + 10;
int t, n, m, k;
int a[maxn];
int cnt;
bool vis[maxn];
bool cmp(int x, int y)
{
    return x > y;
}

bool dfs(int step, int curLen, int maxLen, int num)
{
    if (num >= cnt)
        return true;
    if (curLen == maxLen)
        return dfs(0, 0, maxLen, num + 1);
    int fail = 0;
    for (int i = step; i < n; i++)
    {
        if (!vis[i] && a[i] != fail && (curLen + a[i] <= maxLen))
        {
            vis[i] = true;
            if (dfs(i + 1, curLen + a[i], maxLen, num))
            {
                return true;
            }
            vis[i] = false;
            fail = a[i];
            if (curLen == 0 || curLen + a[i] == maxLen)
                return false;
        }
    }
    return false;
}
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    while (scanf("%d", &n) && n)
    {
        int sum = 0;
        for (int i = 0; i < n; i++)
        {
            scanf("%d", &a[i]);
            sum += a[i];
        }
        sort(a, a + n, cmp);
        for (int i = a[0]; i <= sum; i++)
        {
            if (sum % i)
                continue;
            cnt = sum / i;
            memset(vis, 0, sizeof(vis));
            if (dfs(0, 0, i, 0))
            {
                printf("%d\n", i);
                break;
            }
        }
    }
    return 0;
}