Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
两个简单的剪枝:考虑每次放的第一个和最后一个小木棍就能过了。用了五个月,终于AC,庆祝一下……RT, dfs不解释,假如要把长为a[0...n]小木棍拼成X个长L的大木棍: 当然了,从大到小放是肯定的 剪枝一: 拼每个长为L的大木棍时,第一次若放最大的小木棍,后面拼不上,直接结束函数(return;) 原因很好理解,若最大的小木棍放到这拼不上,放到后面的肯定也拼不上 剪枝二: 拼某个大木棍时,若放入某个小木棍 正好拼完L的长度,后面拼不上,直接结束函数(return;) 因为固定长度,放一个整个的小木棍一定不比放几个零碎的小木棍差 只加这两个剪枝就可以秒掉了 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator