洛谷 - P1120 小木棍

#题面

#题目描述

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 $50$。

现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。

给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。

#输入格式

第一行是一个整数 $n$，表示小木棍的个数。 第二行有 $n$ 个整数，表示各个木棍的长度 $a_i$。

#输出格式

输出一行一个整数表示答案。

#输入输出样例

样例输入 #1

9
5 2 1 5 2 1 5 2 1

样例输出 #1

6

#数据范围与提示

对于 $100\%$ 的测试点，$1 \leq n \leq 65$，$1 \leq a_i \leq 50$。

#思路

搜索，大力剪枝。

提示：请区分好下文中「长棍」和「木棍」的区别，前者指拼接出的成品木棍，后者指题目中提供的被砍断的小木棍。

1. 显然，一根长木棍的灵活性一定比一根短木棍要小，那么需要先尽可能地使用掉长木棍，再使用短木棍填补空缺。

   23 24 25 26 27 28 29 30 31

   for (int i = 1; i <= n; i++) { if (!vis[i]) { vis[i] = true; dfs(now + 1, i, l - a[i]); vis[i] = false; break; } }

   36 37 38 39

   for (int i = p; i <= n; i++) { if (!vis[i]) { vis[i] = true; dfs(now, i, rest - a[i]);

   66 67 68 69 70 71

   for (l = a[1]; l <= sum / 2; l++) { if (sum % l) continue; m = sum / l; dfs(1, 1, l - a[1]); }

   优先使用未使用的木棍中最长的那根。

2. 当第一根长度为 $x$ 的木棍拼接失败之后就不能再使用其他相同长度的木棍了，直接跳到下一个长度即可。

   36 37 38 39 40 41 42 43 44 45

   for (int i = p; i <= n; i++) { if (!vis[i]) { vis[i] = true; dfs(now, i, rest - a[i]); vis[i] = false; if (rest == a[i]) return; i = next[i]; } }

3. 由于原始长度是从小到大枚举的，所以第一次搜索到的答案就是最小长度，直接输出答案并结束程序即可。

4. 如果当前长棍剩余的未拼长度等于当前木棍的长度，继续拼下去时却失败了，就直接回溯不再继续。

   36 37 38 39 40 41 42 43 44 45

   for (int i = p; i <= n; i++) { if (!vis[i]) { vis[i] = true; dfs(now, i, rest - a[i]); vis[i] = false; if (rest == a[i]) return; i = next[i]; } }

   当前长棍剩余的未拼长度等于当前木棍的长度时，显然这根木棍拼到当前长棍上最优（短木棍留到后面插缝用）。如果在最优情况下继续拼下去还是失败了，那么之前肯定有木棍用错了，直接回溯即可。

5. 只选择长度不大于未拼长度 $\mathit{rest}$ 的木棍继续拼接，原因显然。

   33 34 35 36 37 38 39

   // 二分查找第一个长度 <= rest 的木棍所在的位置 int p = std::lower_bound(a + last + 1, a + n + 1, rest, std::greater<int>()) - a; for (int i = p; i <= n; i++) { if (!vis[i]) { vis[i] = true; dfs(now, i, rest - a[i]);

#代码

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76

#include <iostream>
#include <algorithm>
#include <functional>
#include <numeric>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 70;

int n, m, l, a[N], next[N];
bool vis[N]{false, true};

void dfs(int now, int last, int rest) {
    if (!rest) {
        if (now == m) {
            cout << l << endl;

            exit(0);
        }

        for (int i = 1; i <= n; i++) {
            if (!vis[i]) {
                vis[i] = true;
                dfs(now + 1, i, l - a[i]);
                vis[i] = false;

                break;
            }
        }
    }

    int p = std::lower_bound(a + last + 1, a + n + 1, rest, std::greater<int>()) - a;

    for (int i = p; i <= n; i++) {
        if (!vis[i]) {
            vis[i] = true;
            dfs(now, i, rest - a[i]);
            vis[i] = false;

            if (rest == a[i]) return;
            i = next[i];
        }
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    int sum = std::accumulate(a + 1, a + 1 + n, 0);

    std::sort(a + 1, a + 1 + n, std::greater<int>());

    for (int i = n; i; i--) {
        next[i] = a[i] == a[i + 1] ? next[i + 1] : i;
    }

    for (l = a[1]; l <= sum / 2; l++) {
        if (sum % l) continue;  // 不能拼出整数根长棍时就跳过

        m = sum / l;
        dfs(1, 1, l - a[1]);
    }

    cout << sum << endl;

    return 0;
}