【解题报告】洛谷P1120 小木棍

题目链接

https://www.luogu.com.cn/problem/P1120

思路

——摘自《算法竞赛进阶指南》

我们可以从小到大枚举原始木棒的长度 lenlen , 它应该是所有木棍长度的和 sumsum 的因数，并且原始木棒的根数 cntcnt 应该等于 sumlen\dfrac {sum} {len}

对于每一个枚举的 lenlen ，我们可以一次搜索每根原始木棒由哪些木棍拼成，具体的讲，也就是搜索的状态是 ：已经拼好的原始木棒的数量，正在拼的原始木棒的当前长度，每个木棍的使用情况，在么一个状态下，我们从还没有用的木棍中选择一个，尝试拼到当前的原始木棒中，然后递归到新的状态，递归边界就是成功拼好 cntcnt 根原始木棒，或者因为无法继续拼接而失败

这个算法的效率比较低，我们可以进行几类剪枝：

  1. 优化搜索顺序

把木棒从大到小排序，优先尝试比较长的木棍

  1. 排除等效冗余

可以限制先后加入一根原始木棒的木棍长度是递减的，这是因为先拼上一根长度为 xx 的木棍，再拼上一根长度为 yy 的木棍，和先拼 yy 再拼 xx 一毛一样，所以只用搜索其中一种

对于当前的原始木棒，记录最近一次尝试拼接的木棒的长度，如果分支搜索失败回溯，就不再尝试向该木棒中拼接其他相同的木棒，因为必定也会失败

如果当前原始木棒中，尝试拼入的第一根木棍的递归分支就失败了，那这个分支肯定失败，立马回溯，这是因为在拼入这根木棒之前，面对的所有的木棍都是空的，这些木棒都是等效的，木棍拼在当前的木棒里面失败，拼在其他的木棒里面也一定会失败

如果在当前的原始木棒里面拼入一根木棍之后，木棒恰好被拼接完整，并且接下来拼接剩余原始木棒的递归分支返回失败，那么就直接判定当前的分支失败，立即回溯，该剪枝可以使用贪心来解释，再用1根木棍敲好拼完当前的原始木棒必然比再用若干根木棍拼完当前的木棒更加好

这样运用一些等效性和贪心就剪掉了搜索树上面的很多分支，提高了搜索的效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
const int maxn=3300;
int n,ans,res,tot,mx,sum;
int s,l;
int a[70];
bool vis[maxn];
bool dfs(int now,int len,int cnt)
{
	if(now>s) return true;
	if(len==l)
	return dfs(now+1,0,1);
	int f=0;
	for(int i=cnt;i<=tot;i++)
	{
		if(!vis[i]&&len+a[i]<=l&&f!=a[i])
		{
			vis[i]=true;
			if(dfs(now,len+a[i],i+1))
			return true;
			f=a[i];
			vis[i]=false;
			if(len==0||len+a[i]==l)
			return false;
		}
	}
	return false;
}
int main()
{
	std::ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		int x;
		cin>>x;
		if(x>50) continue;
		a[++tot]=x;
		mx=max(mx,x);
		sum+=x;
	}
	sort(a+1,a+tot+1);
	reverse(a+1,a+tot+1);
	for(l=mx;l<=sum;l++)
	{
		if(sum%l) continue;
		s=sum/l;
		memset(vis,false,sizeof(vis));
		if(dfs(1,0,1))
		break;
	}
	cout<<l<<'\n';
	return 0;
}