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 pgy001 at 2016-08-03 13:45:43 on Problem 1083
如果本题求得是搬一次最多搬几个区间的话,不限定所有区间必须搬完,可以用贪心法,使按t从小到大排序,选取第一个区间,然后遍历一遍,找到所有不相交区域。但是本题要求的是所有的区域搬动的最小时间,局部最优相加将不一定得到全局最优,所以,考虑按s排序,尽管每次不会是局部最优,但是,考虑到需要一直搬动,直到所有房屋都搬完,则每次从最小的区间左端s开始,找到不相交区域,具有左一致性,不会交叉,所以可以达到全局最优。
较为严谨的证明,尚且未知,希望大牛帮忙解答!

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