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

这题精度是大坑,WA的人进来看下

Posted by lzqxh at 2012-04-08 11:30:03 on Problem 3155 and last updated at 2012-04-08 11:38:01
首先,这个题目虽然也满足一般分数规划的性质,但是他的曲线比较奇怪是一直为0,然后突然增长,我们2分找到突然增长的点时候,即为其最大密度。
但是,在这一个点的时候,不仅仅最大闭合权的值实现从0到正的突变,方案也存在着突变!这就意味着如果你无限逼近这个点的时候,那你解出来的方案可能是错的,最优解可能是存在由这个点继续增长一点点之后产生的。。所以,我们可以对于二分过程每个mid除了求出闭合权图到值,顺便求出方案,并保留最优方案,而不是2分完成之后再求方案

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