[Luogu P1120]小木棍·加强版

#\(\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\)

上一篇:Java集合之LinkedList源码分析


下一篇:MySQL数据库 常用操作