Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

两个简单的剪枝:考虑每次放的第一个和最后一个小木棍就能过了。用了五个月,终于AC,庆祝一下……

Posted by JokerKS at 2010-10-10 12:45:34 on Problem 1011
RT,
dfs不解释,假如要把长为a[0...n]小木棍拼成X个长L的大木棍:
当然了,从大到小放是肯定的
剪枝一:
拼每个长为L的大木棍时,第一次若放最大的小木棍,后面拼不上,直接结束函数(return;)
原因很好理解,若最大的小木棍放到这拼不上,放到后面的肯定也拼不上
剪枝二:
拼某个大木棍时,若放入某个小木棍 正好拼完L的长度,后面拼不上,直接结束函数(return;)
因为固定长度,放一个整个的小木棍一定不比放几个零碎的小木棍差

只加这两个剪枝就可以秒掉了

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator