0
已解决
资深天翼
如题
3
已采纳
高级光能
总得来说就是剪枝DFS:枚举最小长度,进行拼凑.
几个剪枝:
-
枚举最小长度时(设为len),可得:min(小木棍长度)<=len<=小木棍总长,同时(总长 mod len=0).
-
当每次接入小木棍后,大木棍未达到要求长度时,下一个接入的小木棍取比刚刚接入的小木棍短的小木棍.
-
当一个小木棍接入后,当前处理的大木棍刚好达到要求的长度的话,没必要用更多的小木棍代替这个刚接入的小木棍,因为更短的小木棍比它有更大的适用性(所以把它们留在后面用必定比接入这里更好).
- 当处理完一个大木棍之后,接入下一个大木棍的第一根小木棍用剩下的最长的小木棍.
几个处理:
-
枚举最小长度时由小到大枚举,找到第一个后直接输出就可以HALT了.
- 将所有木棍由大到小排序,以便剪枝.
注意事项:
题目说:"直到每段的长都不超过50",所以去掉超过50的小木棍
0
初级天翼
h
0
资深守护
1
0
新手启示者
1
0
高级天翼
不会。
0
资深光能
二分答案+DFS
0
缔造者
1
0
高级守护
C++
0
资深天翼
对llr大神如此大不敬，斩首！
0
初级天翼
不会
0
资深守护
不会
