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

剪枝的原理

Posted by yfsyfs at 2019-08-18 20:45:13 on Problem 3172
其实我们知道唯一的剪枝手段就是如果当前价值+剩下物品的价值之和<当前ans的话, 就剪枝. 所以想要快速剪枝最好的办法就是快速增大ans. 而快速增大ans的手段就是ac代码做的——从价值最大的开始(注意,因为本题特殊性,每个物品的价值=耗费)深搜. 而且先考虑放,后考虑不放. 就能实现快速增大ans进而提高剪枝效率, 从而ac.

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