难度：提高+/省选-

题目描述

        乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过50。
        现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
        给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

输入输出格式

输入格式:

        共二行。
        第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤65。
        第二行为N个用空个隔开的正整数，表示N根小木棍的长度。

输出格式:

        一个数，表示要求的原始木棍的最小可能长度。

输入输出样例

Sample input

9
5 2 1 5 2 1 5 2 1

Sample output

6

题解

        题目考察DFS及剪枝，对搜索和剪枝能力要求很高。
        输入时过滤掉大于50的数据。
        易知最小的木棍长度可能值一定不小于当前木棍长度的最大值，不大于所有木棍长度的和。从可能的最小值开始只到最大值依次检验，但凡找到一个值可行，该值显然最小，输出该值并结束程序。另外答案只可能是长度和的因子，非因子直接continue即可。
        检验方式为DFS，从搭建第一个木棍开始，遍历所有尚未访问的木棍数值，将其加入到新的木棍中。若所有木棍都可以加入到新木棍中以拼成若干根等长的木棍，则该值可行。这样的做法时间复杂度相当高，极易超时。
        由于值只有在DFS完成后才可以知道其可行性，并且得到最值后立即结束程序，我们不可在DFS过程中通过值的最优性剪枝。下面探讨其它剪枝方法。
        自排序原则：每一根新的长木棍是由许多小木棍组成的，本质上是若干个数相加，这些数之间一定有次序关系。由于我们只考虑它们的和而并不关心它们的次序，所以可以规定每一个长木棍由若干长度递减的木棍组成，从而避免很多次序不同但本质相同的组合。这里不推荐升序排列，这是因为较小的木棍有更高的机动性，升序后每一个新的长木棍末端都由较长的木棍组成，由于较长的木棍机动性差，会导致频频回溯，最终使程序性能下降。
        第一剪枝法则：一个待完成的长木棍在加入一根木棍后刚好完成，若在此基础上拼凑剩余长木棍不可行，则用其他木棍拼凑该待完成长木棍一定也是不可行的。结论证明:已知剩余长度为a1，a2，…，an的木棍，在加入ai后刚好拼凑了一根长木棍，之后用剩余的n-1根木棍拼凑剩下的长木棍不可行。假设加入ap1，ap2，…，aps这s根木棍(满足ap1+ap2+…+aps=ai)后拼凑好了最初的长木棍，剩下的n-s根木棍同样可以拼凑剩下的长木棍。这n-s根木棍中必有ai，此时交换ai和ap1，ap2，…，aps的位置，这显然是一种可行的方案，与已知条件矛盾，从而得证其余拼凑方案必不可行。
        第二剪枝法则：对于一根完全没有完成的长木棍(长度为0)，向其中加入一根木棍，若在此基础上不可行，则向其中加入剩余木棍中的任何一个都不可行。该结论证明与第一剪枝法则类似，从略。
        结合上述三点策略，容易写出完整DFS代码。
        总结:递归时尽量小起点，避免频繁回溯。另外注意自排序原则，这是很重要的方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<algorithm>

using namespace std;

bool cmp(int x, int y) {
    return x > y;
}

int op[100], n, sum[100] = {0}, vis[100], length, number;

void DFS(int rank, int start, int temp) {
    if (rank == number + 1) {
        cout << length;
        exit(0);
    }
    if (sum[start] < length - temp)return;
    int t = 100;
    for (register int i = start; i <= n; i++) {
        if (vis[i])continue;
        if (op[i] + temp > length)continue;
        if (t == op[i])continue;
        vis[i] = 1;
        t = op[i];
        if (op[i] + temp == length) {
            DFS(rank + 1, 1, 0);
            vis[i] = 0;
            return;
        } else DFS(rank, i + 1, temp + op[i]);
        vis[i] = 0;
        if (!temp)return;
    }
}

int main() {
    cin >> n;
    int j = 1;
    for (register int i = 1; i <= n; i++) {
        cin >> op[j];
        if (op[j] <= 50)j++;
    }
    n = j - 1;
    sort(op + 1, op + n + 1, cmp);
    for (register int i = n; i >= 1; i--)sum[i] = op[i] + sum[i + 1];
    for (register int i = n; i >= 1; i--) {
        if (sum[1] % i != 0)continue;
        memset(vis, 0, sizeof(vis));
        length = sum[1] / i, number = i;
        DFS(1, 1, 0);
    }
    return 0;
}