BZOJ1857, HDU3400 – 传送带问题(三分套三分)

OI中有种暴力的解法就是把区间离散化,是可以过部分数据的。

在搞清这题的AC算法之前先要搞清一个问题,如何求单峰函数的极值。



假设我们要求一个单峰函数 $ f(x) $ 在区间 $ [a,b] $ 上的极值,如图所示。函数图像上两点 $ P(x_p,y_p) , Q(x_q,y_q) $ 保证 $ [x_p,y_p] ⊂ [a,b] $。因为函数是单峰的,如果有 $ y_p > y_q $,则可以断定极值点一定不在 $ P $ 左边。这一点很重要。这意味着我们可以缩小区间范围。缩小范围的方法就是把区间不断三分,比较两个分点,舍去三个区间其中一个子区间。当区间长度小于一个绝对小的数的时候,我们可以认为找到了这个极值点,当然这个绝对小的数也是人为定义的,它可以是1E-4等等。

那么我们再来看这一题。为了达到最少的时间,首先不能出现来回走的路径,所以我们的路径一定是这样的:经过AB上一点S,经过CD上一点T,整个路径就是A->S->T->D,下面我们考虑如何让这条路径最优(时间最短)。



假设S是一个定点,那么我们只要考虑路径S->T->D最优,通过画图可以发现这条路径所用的时间关于T点位置的函数是单峰的,也就是说T点的位置如果从C到D一一枚举,耗费的时间会经过一个先递减再递增的过程(这里的单峰有猜测的因素,不过也可以给出严格的证明),那么要找到这条路径的最优解,需要对CD线段进行三分。

同理,S作为动点时,路径A->S->T->D耗费的时间关于S点位置的函数也是单峰的。所以我需要对AB线段进行三分,确定最优的S点。因此,水到渠成,三分套三分。

 

2
说点什么

avatar
50
1 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
YuweiZhaoVel Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
Vel
游客

图挂了。。。