#\(\mathcal{Description}\)
乔治有一些同样长的小木棍,他把这些木棍随意砍成几段,直到每段的长都不超过 \(50\) 。
现在,他想把小木棍拼接成原来的样子,但是却忘记了自己开始时有多少根木棍和它们的长度。
给出每段小木棍的长度,编程帮他找出原始木棍的最小可能长度。
#\(\mathcal{Solution}\)
\(hhhh\)这题可真是毒瘤啊\(qwq\)。
首先我们先考虑如何\(dfs\),即\(dfs\)时的状态:
1、摆好了几根 2、当前这根还剩的长度 3、当前\(dfs\)是要从哪一根开始摆。
好的,这样会\(T\)飞,所以我们考虑剪枝。
·由于是要全部用光,所以长度一定是总长度的某个因子;而又因为每根木棍至少满足\(\leq\)原始长度,所以我们可以在全部的因子里面二分出一个下界,那么就是这样
for(i = 1; i <= N; i ++){
scanf("%d", &a) ;if(a > 50) continue ;
w[++ cnt] = a, tot += w[cnt], maxn = max(maxn, w[cnt]) ;
}
s = sqrt(tot) ;
for(i = 1; i <= s; i ++) if(!(tot % i)) base[++ total] = i, base[++ total] = tot / i;
sort(w + 1, w + cnt + 1, cmp) ;
base[++ total] = tot ; sort(base + 1, base + total + 1) ;
pos = lower_bound(base + 1, base + total + 1, maxn) - base ;
·但这还不够,我们可以考虑从大到小枚举木棍,因为这样会减少很多无用状态。\(emmm\)写在上面的代码里了。
然而还是\(T\),于是就去瞅了几眼题解,发现在\(dfs\)里面还有很多小优化,比如长度的单调性决定了我们可以舍弃部分状态, 比如如果当前的长度最大都不行,或者已经要开始下一根木棍,那么就直接\(break\).
真是个玛丽题啊\(qwq\)