社区首页 >专栏 >【题解】小木棍(搜索剪枝)

【题解】小木棍(搜索剪枝)

fishhh

发布于 2022-08-30 11:31:39

40800

代码可运行

文章被收录于专栏：OI算法学习笔记OI算法学习笔记

运行总次数：0

代码可运行

题目描述

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

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

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

输入格式

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

。

输出格式

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

输入输出样例

输入 #1

9
5 2 1 5 2 1 5 2 1

输出 #1

说明/提示

对于全部测试点，

题目分析

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

首先，暴力搜索。尝试将所有的木棍进行拼接。可以给定一个假想的原始木棍长度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]不满足要求了，和他长度相同的小木棍也一定不满足要求
木棍越短，能够拼的可能性也就越多，可以先从长的小木棍开始拼接，减少搜索次数
如果搜索后发现长度不合适，且剩余长度等于原始木棍长度，说明之前的选择有问题，可以直接回溯。因为长木棍直接拼上去不合适的话，后面的小木棍无论如何也不可能符合要求。
如果搜索后发现长度不合适，且该长度等于剩余长度

代码实现

#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;
}