BZOJ-3695. 滑行

这是 2014 年福建省省队训练的时候首长出的一道题,然后听完讲评后整个人就不好了,题目大概是这样的

首长NOI惨跪,于是去念文化课了。现在,他面对一道物理题

现在有一个小滑块可以在地面上滑行,地面上被划分成不同的区域,使得小滑块在不同的区域内部有一个不同的速度上限

小滑块在(0,0)点,我们现在要推动小滑块到目标点(x,y)

地面上有 N 层区域,每层区域都是矩形,现在给你一个序列 \{H_i\} 表示每层区域的高度,覆盖的地面横坐标范围是 0~X,第i个区域的限速是 v_i

注: Y=\sum_{i=1}^nH_i,其它的地方小滑块不允许进入

现在我们要设计一个路线使得小滑块滑到目标点的用时最小

如果你知道两个物理学的定理(光的最速原理、折射定律),那么这题就可以很快解出来了

(more…)

Read More