CEOI1995 stick 题解

Edited on | In | Comments:

Problem

问题描述：

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

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

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

输入：

输入文件共有二行。第一行为一个单独的整数$n$表示砍过以后的小木棍的总数，其中$n≤64$，第二行为$n$个用空格隔开的正整数，表示$n$根小木棍的长度。

输出：

输出文件仅第一行，表示原始木棍的最小可能长度。

输入输出样例：

1
2
3
Input #1
9
5 2 1 5 2 1 5 2 1
1
2
Output #1
6

Solution

显然这是一道搜索题。

由于每根原始木棍长度一样，所以答案必然能整除所有木棍总长度，并且不能比最长的那一根短。

搜索的结束条件是 剩下的木棍根数 $=0$ 且 当前原始木棍剩余长度 $=0$。

如果 当前原始木棍剩余长度 $=0$，那么之后的木棍就应放到下一根里去。

具体剪枝方案见代码注释。

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
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 65;
int n;
int a[MAXN], sum;
int all; //初始长度
bool Visit[MAXN];

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

bool dfs(int last, int left, int depth) //last表示上一次用了哪一根，由于已经排过序，这一次取的木棍一定比上一次短
{
    if (depth == 0 && left == 0) return true; //搜完了，满足条件
    if (depth == 0 && left != 0) return false; //搜完了但不满足条件
    if (left == 0) left = all, last = 1; //这根填满了，重置下一根
    for (int i = last; i <= n; i++) if (a[i] <= left)
    {
        if (Visit[i]) continue; //已经用过了
        if (i > 1 && !Visit[i - 1] && a[i] == a[i - 1]) continue; //如果上一根和这一根长度一样，也没能成功，这一根可以不搜
        Visit[i] = true; //标记为已访问
        if (dfs(i, left - a[i], depth - 1)) return true; //递归搜下一根
        Visit[i] = false; //回溯
        if (a[i] == left || left == all) return false;
        /*
        已知放这根木棍不成功，那么分两类讨论：
          1.若放好这一根正好能填满当前原始木棍，而剩下的木棍无法填满之后的原始木棍，则之后搜的结果和本次搜的一样，都无法完成，回溯；
          2.若当前原始木棍是一根新木棍，则亦无法完成，原因同上。
          这层剪枝十分重要，但较为难想。
        */
    }
    return false;
}

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i], sum += a[i];
    sort(a + 1, a + n + 1, cmp);
    for (int i = a[1]; i <= sum / 2; i++) if(sum % i == 0) //能整除
    { all = i; if (dfs(1, i, n)) { cout << i << endl; return 0; } } //找到答案
    cout << sum << endl;
    return 0;
}

Data

测试数据 提取码：3gag

无注释代码也一起放了进去，供大家参考。