时间戳

首页 > 技术文章 > 小木棍

小木棍

hihocoder 2019-08-20 08:38 原文

Description

乔治有一些同样长的小木棍，他把这些木棍随意砍成几段，直到每段的长都不超过100。现在，他想把小木棍的长度，编程帮他找出原始木棍的最小可能长度。

Input

第一行为一个单独的整数N表示砍过以后的小木棍的总数，其中N≤60，第二行为N个用空格隔开的正整数，表示N根小木棍的长度

Output

输出文件仅一行，表示要求的原始木棍的最小可能长度。

Sample Input

7
63 2 44 12 60 35 60

Sample Output

276

题解

经典的搜索题，对于\(N≤60\)的数据肯定需要大量的减枝。

我们由小到大搜索原木棍的长度，Dfs判断是否可行，由大到小枚举小木棍能否拼接，因为小的灵活性更强。

  • 减枝一(上下界减枝)：由于本题搜索范围不确定，所以我们可以就搜索的上下界进行减枝。搜索的上界为所有木棍的总长度，即原木棍只有一根，这种情况必然存在。搜索的下界即为最长的小木棍的长度

  • 减枝二：当总长度\(%\)当前枚举的原木棍的长度不为\(0\)时，枚举的原木棍的长度必然不是原木棍的可行长度

  • 减枝三：当当前尝试的小木棍的长度等于上次尝试的小木棍的长度时，不进行尝试

  • 减枝四(难点)：当当前小木棍为新的原木棍的第一个时，若后面的拼接尝试失败，则前面的拼接方式绝对不行，因为这根小木棍必然要拼在接下来的几根原木棍上，而这时却拼接失败。当当前小木棍加上已拼接的长度刚好等于原木棍时，若后面的拼接尝试失败，则前面的拼接方式也是不行的，因为要想拼接成功，则已拼接的长度必然要加上这个小木棍的长度，这个小木棍的不行，比它小的即使能拼接出这个长度，也会不行，因为小的灵活性更强

现在可以轻轻松松的上代码了：

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

const int N=100;
int n,l[N],suml,maxl,len,numl;//suml记录l[]的总长，maxl记录最大长度
bool use[N];

bool Cmp(int a,int b){return a>b;}

void  Read()//读入
{
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&l[i]),suml+=l[i],maxl=max(maxl,l[i]);
	sort(l+1,l+n+1,Cmp);//从大到小排序
}

int Dfs(int nw,int nl,int lt)//nw表示当前拼接的原小木棍，nl表示当前拼接的原小木棍的已拼长度，lt表示上一根小木棍用的是第几个
{
	if(nw>numl) return 1;//拼接完毕
	if(nl==len) return Dfs(nw+1,0,1);//当前拼接的原小木棍已拼完
	int fail=0;
	for(int i=lt;i<=n;++i)
		if((!use[i])&&(nl+l[i]<=len)&&(fail!=l[i]))//减枝三
		{
			use[i]=1;
			if(Dfs(nw,nl+l[i],i+1)) return 1;
			use[i]=0;
			if((!nl)||(nl+l[i]==len)) return 0;//减枝四
			fail=l[i];
		}
	return 0;
}

void Solve()
{
	for (int i=maxl,suml2=suml/2;i<=suml2;++i)//减枝一
	{
		if(suml%i)continue;//减枝二
		numl=suml/i,len=i;//numl为原小木棍的个数，len原小木棍的长度
		if(Dfs(1,0,1)) {printf("%d\n",i);return;}
	}
	printf("%d\n",suml);
}

int main()
{
	Read(),Solve();
	return 0;
}

推荐阅读