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 |
这题精度是大坑,WA的人进来看下首先,这个题目虽然也满足一般分数规划的性质,但是他的曲线比较奇怪是一直为0,然后突然增长,我们2分找到突然增长的点时候,即为其最大密度。 但是,在这一个点的时候,不仅仅最大闭合权的值实现从0到正的突变,方案也存在着突变!这就意味着如果你无限逼近这个点的时候,那你解出来的方案可能是错的,最优解可能是存在由这个点继续增长一点点之后产生的。。所以,我们可以对于二分过程每个mid除了求出闭合权图到值,顺便求出方案,并保留最优方案,而不是2分完成之后再求方案 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator