poj 1011 Sticks-技术圈

Sticks

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 170210		Accepted: 41153

Description

George took sticks of the same length and cut them randomly until all parts became at most 50 units long. Now he wants to return sticks to the original state, but he forgot how many sticks he had originally and how long they were originally. Please help him and design a program which computes the smallest possible original length of those sticks. All lengths expressed in units are integers greater than zero.

Input

The input contains blocks of 2 lines. The first line contains the number of sticks parts after cutting, there are at most 64 sticks. The second line contains the lengths of those parts separated by the space. The last line of the file contains zero.

Output

The output should contains the smallest possible length of original sticks, one per line.

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5

棒

描述

乔治拿着相同长度的木棍，随机地把它们切下来，直到所有部分的长度不超过50单位。现在他想把木棍放回原来的状态，但他忘了原来有多少根木棍和它们原来的长度。请帮助他，设计一个程序来计算那些棒的最小原始长度。所有以单位表示的长度都是大于零的整数。

输入

输入包含2行的块。第一行包含了切割后木棍部分的数量，最多64个木棍。第二行包含由空格分隔的部分的长度。文件的最后一行包含0。

输出

输出应该包含原始棒的最小长度，每行一个。

Sample Input

9
5 2 1 5 2 1 5 2 1
4
1 2 3 4
0

Sample Output

6
5

棒语十级：请将切成不同长度的棒子拚接起来，做出长度相同的棒子，但是要考虑拚接起来的度必须是最短的。换句话说，就是尽量做出更多长度相同的棒子。
举例来说：

4.5开动脑筋智慧搜索

剪枝

看到《短码之美》上有，那就直接看书吧。

如果是简单地输入，即使做了一些无谓的搜索，也能够求出结果。但是，由于切出来的段数最多有64根，单纯计算所有组合就需要很长时间。这次用一个稍微复杂一点的例子，首先手动求组合看看。

首先，准备下面这样的测试数据。

8 3 8 15 2 11 4 8 1

这9个数值的合计（sum)是60，最大值（max)是15，60的约数中比15大的有15、20、 30、60(=length)这4个，检查切出来的全部片段是不是能够拼出这些长度的棒子。

首先考虑length=15的情况。

将这9个数字降序排列：

15 11 8 8 8 4 3 2 1

从这个清单的开头开始，分割成合计为15的部分。

11，4

8,…

15保持原状，下一个11+4=15,再下一个8加上8就是16 了，超出了 15。即使依次加上3、 2、1还是等于14,凑不上15。所以知道原本棒子的长度不是15。那么下面这组又怎么样呢？

11，3, 1

8,…

同前面那组一样无法凑成15,似乎原本棒子的长度不是15。20能行吗？

15, 4, 1

11，8,…

最初选择{15, 4, 1}就不能拼出第2根棒子了，但是这就说20不行有些太早了。

15,3,2

11，8, 1

8, 8, 4

如果最开始的一组用{15, 3, 2}，就能顺利凑齐长度是20的棒子。接下来把这样的搜索方法用程序代码来实现就可以了。怎样做才好呢？

前面是手动来检査搜索方法，现在可以通过DFS算法来实现。DFS会考虑将输入值（片段的长度）作为顶点，从最幵始的节点开始顺序地建立树形结构（清单）。用图表示就像下面这样。

PKU 1011 Sticks.png

在编写程序之前，先整理一下重点。

1、将数椐按降序排序。

2、从数值最大的开始（=从数组开头幵始），依次减去K度值，直到棒子的长度（length)

变成0为止，同时标记用到的数值。

3、如果长度变成0,则把length恢复原值，再执行②。

4、如果失败，则返回到前一个状态。

5、如果做出sum/length个长度是length的棒子就成功了。

代码：

#include 
using namespace std;
int in[51]; //长度为i的片段个数
int length; //棒子的原始长度
int finish; //终止标志（非0即终止）
/**
 * 遍历
 * @param count 棒子的总数（如果为0，则结束）
 * @param len 目前检查的棒子长度的剩余量
 * @param plen 现在检查的片段长度
 */
void check(int count, int len, int plen)
{
    --in[plen]; //取一个长度是plen的片段来用
    if (count == 0)
        finish = 1;
    if (!finish)
    {
        len -= plen;
        if (len != 0)
        {
            int next_plen = min(len, plen); //剪枝策略：用plen去凑len，next_plen必须是较小者
            for (; next_plen > 0; --next_plen)
                if (in[next_plen])  //有剩余
                    check(count, len, next_plen);
        }
        else
        {
            //片段长度最大为50
            int max = 50;
            while (!in[max])
                --max;
            check(count - 1, length, max);
        }
    }
    ++in[plen]; //恢复原始状态
}

int main()
{
    int n;
    while (~scanf("%d", &n) && n)
    {
        memset(in, 0, sizeof(in));
        int sum = 0;
        int max = 0;
        finish = 0;
        while (n--)
        {
            int b;
            scanf("%d", &b);
            ++in[b];
            sum += b;
            if (max < b)
                max = b;
        }
        length = max;
        while (true)
        {
            if (sum % length == 0)
                check(sum / length, length, max);
            if (finish)
                break;
            ++length;
        }
        printf("%d\n", length);
    }
}