题目描述
乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过 50。
现在，他想把小木棍拼接成原来的样子，但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度，编程帮他找出原始木棍的最小可能长度。
输入格式
第一行是一个整数 n，表示小木棍的个数。 第二行有 n 个整数，表示各个木棍的长度
。
输出格式
输出一行一个整数表示答案。
输入输出样例
输入 #1
代码语言：javascript复制9
5 2 1 5 2 1 5 2 1输出 #1
代码语言：javascript复制6说明/提示
对于全部测试点，
题目分析
给定若干个木棍的长度，他们是由一些一样长的木棍砍断得到的，要求求出原始木棍的最小可能长度。
首先，暴力搜索。尝试将所有的木棍进行拼接。可以给定一个假想的原始木棍长度ori，原始木棍的长度范围是
搜索尝试能否将小木棍进行拼接成若干根长度为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;
}
}
}
会出现多个点超时。此时，我们考虑进行剪枝。
- 原始木棍的长度一定是总长的因子
- 可能出现相同的小木棍，当长度
a[i]不满足要求了，和他长度相同的小木棍也一定不满足要求 - 木棍越短，能够拼的可能性也就越多，可以先从长的小木棍开始拼接，减少搜索次数
- 如果搜索后发现长度不合适，且剩余长度等于原始木棍长度，说明之前的选择有问题，可以直接回溯。因为长木棍直接拼上去不合适的话，后面的小木棍无论如何也不可能符合要求。
- 如果搜索后发现长度不合适，且该长度等于剩余长度
代码实现
代码语言：javascript复制#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
int a[70],n;
bool vis[70];
int cnt[70],nxt[70],les[5000];
void dfs(int ori,int now,int re,int len){//拼接目标 现在差的长度 剩下的木棍数量
// printf("ori:%d now:%d re:%d len:%dn",ori,now,re,len);
if(now==0){//拼完一根原始木棍
dfs(ori,ori,re-1,a[1]);//继续再拼
return ;
}
if(re==0){//全部拼完
printf("%d",ori);
exit(0);
}
//剪枝3 寻找时，从大到小去找小木棍
//找到小木棍中小于等于剩余长度的最大长度
len=min(len,now);
while(len&&cnt[len]==0) len=les[len];
while(len){
if(cnt[len]){
cnt[len]--;
dfs(ori,now-len,re,len);
cnt[len] ;
//剪枝4、5
if(now==ori||now==len) return;
len=nxt[len];//剪枝2 跳过相同木棍，找下一个小木棍
}else{
len=nxt[len];
}
}
}
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>());//从大到小排序
//预处理，nxt[x] 长度小于x的下一个值
for(int i=n;i>=1;i--){
if(a[i]!=a[i 1]){
nxt[a[i]]=a[i 1];
}
}
//预处理 les[x] 小于x的小木棍的最大的长度
for(int i=sum,j=a[1];i>=a[n];i--){
if(i>j){
les[i]=j;
}else{
j=nxt[j];
les[i]=j;
}
}
for(int i=a[1];i<=sum/2;i ){//从最长的小木棍开始找起
if(sum%i) continue;//剪枝1 长度不是总长的因数不予考虑
dfs(i,i,sum/i,a[1]);
}
printf("%d",sum);
return 0;
}
Q.E.D.
