题目链接

洛谷P1120 小木棍

题目描述

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

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

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

输入格式

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

输出格式

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

样例 #1

样例输入 #1

9
5 2 1 5 2 1 5 2 1

样例输出 #1

6

提示

对于全部测试点，$1\le n\le 65$，$1\le a_i\le 50$。

算法思想（暴力枚举+DFS验证）

将一些同样长的小木棍随意砍成几段，然后拼接成原来的样子。给出每段小木棍的长度，求原始木棍的最小可能长度。根据题目描述可以得到下面的性质：

• 原始长度$ans$一定大于等于每段小木棍的长度$a_i$，即 a n s ≥ m a x { a i } ans ge max {a_i} ans≥max{ai​}
• 原始长度$ans$一定小于等于每段小木棍的长度之和$tot$，即$ans\le tot$
• 每段小木棍的长度之和$tot$一定是原始长度$ans$的倍数，即$tot\%ans=0$

基于上面的$3$个性质和数据范围（$1\le n\le 65$，$1\le a_i\le 50$），可以从小到大枚举原始长度$ans$，然后通过DFS验证答案是否合法。验证成功，即找到答案。

为了提高DFS的效率，可以从以下几个方面进行剪枝优化：

1. 优化搜索顺序：对每一种方案，优先使用长木棍进行拼接，即从长到短地将木棍拼接起来。
2. 避免重复搜索：若拼接当前木棍时已用了一根长为$x$的木棍，递归时从上次使用的长度$x$开始继续搜索。
3. 合法性检查：
   a. 使用桶记录每种长度的小木棍的出现次数。DFS枚举每段小木棍长度时，若没有该长度的小木棍或者该长度的小木棍都已使用完了，剪枝。
   b. 当前拼接的长度$len$加上要拼接的小木棍长度$i$超过原始长度$ans$时，剪枝。
4. 可行性剪枝：使用长度为$i$的小木棍拼接失败时，检查
   a. 如果已拼接的长度$len$为$0$，说明当前小木棍无法完成拼接
   b. 如果拼接的长度$len$与枚举的长度$i$之和为原始长度时，其它更短的小木棍无法完成拼接
   结束搜索当前方案。

代码实现

#include <iostream>
using namespace std;
const int N = 100;
//b[i]表示长度为i的木棍个数
int minx = N, maxx, tot, b[N];
//一共拼k根原始木棍，当前已拼好的长度为len
//x表示当前使用的木棍的最大长度，ans表示木棍的原始长度
int dfs(int k, int len, int x, int ans) {
    //拼完所有原始木棍
    if(k == 0) return 1;
    //如果已拼好的长度等于原始木棍长度时，就拼下一个
    if(len == ans) return dfs(k - 1, 0, maxx, ans);
    //1.优化搜索顺序，从长到短地将木棍拼接起来
    //2.避免重复搜索，递归时从上次使用的长度x开始继续搜索
    for(int i = x; i >= minx; i --) {
        //3.合法性检查，如果不存在长度为i的木棒，或着拼完后长度超过原始木棍的长度
        if(b[i] == 0 || len + i > ans) continue;
        b[i] --; //使用了一根长度为i的木棍
        if(dfs(k, len + i, i, ans)) return 1;
        b[i] ++; //回溯，恢复状态
        //4.可行性剪枝
        if(len == 0 || len + i == ans) break;
    }
    return 0;
}
int main()
{
    int n, x;
    scanf("%d", &n);
    while(n --) {
        scanf("%d", &x);
        if(x > 50) continue;
        b[x] ++; //长度为x的木棍个数增加1
        tot += x; //累加所有木棍的长度
        maxx = max(maxx, x);
        minx = min(minx, x);
    }
    //枚举原始木棍的长度
    int ans;
    for(int i = maxx; i <= tot; i ++) 
    {
        //原始木棍的长度应该是总长度的约数
        if(tot % i != 0) continue; 
        //一共可以拼tot / i 根原始木棍，开始拼接的长度为0
        //每次搜索时从最长的木棍maxx开始拼
        //要拼的原始木棍的长度为i
        if(dfs(tot / i, 0, maxx, i)) 
        {
            ans = i;            
            break;
        }
    }
    printf("%d", ans);
    return 0;
}