题目描述

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

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

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

输入格式

第一行是一个整数 n,表示小木棍的个数。
第二行有 nn 个整数,表示各个木棍的长度 aia_i

输出格式

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

输入输出样例

输入 #1

9
5 2 1 5 2 1 5 2 1

输出 #1

6

说明/提示

对于全部测试点,1n651 \leq n \leq 651ai501 \leq a_i \leq 50

题目分析

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

​ 首先,暴力搜索。尝试将所有的木棍进行拼接。可以给定一个假想的原始木棍长度ori,原始木棍的长度范围是 max(ai)summax(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 cnt[70],nxt[70],les[5000];
void dfs(int ori,int now,int re,int len){//拼接目标 现在差的长度 剩下的木棍数量 
	//	printf("ori:%d now:%d re:%d len:%d\n",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.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)