题目描述
乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过 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;
}
}
}
会出现多个点超时。此时,我们考虑进行剪枝。
- 原始木棍的长度一定是总长的因子
- 可能出现相同的小木棍,当长度
a[i]
不满足要求了,和他长度相同的小木棍也一定不满足要求 - 木棍越短,能够拼的可能性也就越多,可以先从长的小木棍开始拼接,减少搜索次数
- 如果搜索后发现长度不合适,且剩余长度等于原始木棍长度,说明之前的选择有问题,可以直接回溯。因为长木棍直接拼上去不合适的话,后面的小木棍无论如何也不可能符合要求。
- 如果搜索后发现长度不合适,且该长度等于剩余长度
代码实现
#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;
}