题目描述

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

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

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

输入格式

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

输出格式

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

输入输出样例

输入 #1

9
5 2 1 5 2 1 5 2 1

输出 #1

6

说明/提示

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

题目分析

​ 给定若干个木棍的长度，他们是由一些一样长的木棍砍断得到的，要求求出原始木棍的最小可能长度。

​ 首先，暴力搜索。尝试将所有的木棍进行拼接。可以给定一个假想的原始木棍长度ori，原始木棍的长度范围是 $max(a_i) \sim sum$ 搜索尝试能否将小木棍进行拼接成若干根长度为ori的长木棍。设dfs(ori,now,re) 表示原始木棍长ori，当前的长木棍还剩now需要拼接，还剩re根木棍需要拼接。

void dfs(int ori,int now,int re){//拼接目标 剩下的木棍数量
    if(now==0){//一根长木棍拼接成功
        if(re==0){//所有小木棍都用完
            printf("%d",ori);//输出答案
            exit(0);            
        }else{
            dfs(ori,ori,re);//继续再拼下一个长木棍
            return ;
        }
    }
    for(int i=1;i<=n;i++){//遍历所有的木棍
        if(!vis[i]&&a[i]<=now){//找到能用的小木棍
            vis[i]=true;
            dfs(ori,now-a[i],re-1);//递归，拼接下一根
            vis[i]=false;
        }
    }
}

会出现多个点超时。此时，我们考虑进行剪枝。

1. 原始木棍的长度一定是总长的因子
2. 可能出现相同的小木棍，当长度a[i]不满足要求了，和他长度相同的小木棍也一定不满足要求
3. 木棍越短，能够拼的可能性也就越多，可以先从长的小木棍开始拼接，减少搜索次数
4. 如果搜索后发现长度不合适，且剩余长度等于原始木棍长度，说明之前的选择有问题，可以直接回溯。因为长木棍直接拼上去不合适的话，后面的小木棍无论如何也不可能符合要求。
5. 如果搜索后发现长度不合适，且该长度等于剩余长度

代码实现

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int a[70],n;
bool vis[70];
int m;
int nxt[70];//nxt[x] 长度小于x的下一个小木棍的长度
int les[5000],cnt[5000];
/*
1. 原始木棍的长度 一定是 总长的因子
2. 可能存储相同的小木棍，当长度a[i]不满足要求，和他一样长的小木棍也一定不符合要求
3. 木棍越短，能够拼接的可能性也就越多，可以先从长的小木棍开始拼接，减少整体搜索次数。

4. 如果搜索后发现长度是不合适，且剩余的长度等于原始木棍长度。
说明之前的选择存在问题，可以直接回溯。
5. 如果搜索后发现长度是不合适,且该长度等于剩余的长度

*/
void dfs(int ori,int now,int re,int st){//拼接目标 当前木棍待拼接长度 剩余拼接的
    if(now==0){//一根长木棍拼接成功
        dfs(ori,ori,re-1,1);
        return ;
    }
    if(re==0){//全部拼完
        printf("%d",ori);
        exit(0);
    }
    //剪枝3 寻找时，从大到小去找小木棍
    //找到小木棍中小于等于剩余长度的最大长度
    for(int i=st;i<=m;i++){
        if(!cnt[a[i]] || a[i]>now) continue;
        cnt[a[i]]--;
        dfs(ori,now-a[i],re,i);
        cnt[a[i]]++;
        if(now==ori || a[i]==now) return ;//优化4，5
    }
}
int main(){
    int sum=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        sum+=a[i];//求和
        cnt[a[i]]++;//记录a[i]个数
    }
    sort(a+1,a+1+n,greater<int>());//从大到小排序
    m=unique(a+1,a+1+n)-a-1;//用unique 进行去重
    for(int i=a[1];i<=sum;i++){//从最长的小木棍开始找起
        if(sum%i) continue;//长度不是总长的因数不予考虑 可行性优化 //优化1
        dfs(i,i,sum/i,1);
    }
    printf("%d",sum);
    return 0;
}