BZOJ-3695. 滑行

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

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

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

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

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

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

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

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

光的最速原理是说,光从一点射到另一点,用的路径一定是所有路径中最短的

折射定律是说,光的入射角 \theta_1 和折射角 \theta_2 与光在两块介质中的速度 v_1,~v_2 有如下关系:

\frac{\sin\theta_1}{v_1}=\frac{\sin\theta_2}{v_2}

这样,把滑块类比成光,就可以二分初始角度来计算答案了

但是…… 如果不知道上面那两个东西怎么办呢?

那我们只能乖乖的来用数学推导了

首先设入射角为 \theta_1,折射角为 \theta_2,在两块区域的速度分别是 v_1,~v_2,两块区域的高度分别是 h_1,~h_2

那么要求的就是最小化

 f(\theta_1, \theta_2) = \frac{h_1}{v_1\cos\theta_1}+\frac{h_2}{v_2\cos\theta_2}

并且还有一个限制条件

 h_1\tan\theta_1 + h_2\tan\theta_2 = d

于是问题变成了求有约束条件的优化问题,数学上有一种叫做拉格朗日乘数法的东西,可以用来解决这个问题

也就是设

\Phi(\theta_1, \theta_2) = h_1\tan\theta_1 + h_2\tan\theta_2 - d

F(\theta_1, \theta_2) = f(\theta_1, \theta_2) + \lambda \Phi(\theta_1, \theta_2)

这样,当 f(\theta_1, \theta_2) 在限制条件 \Phi(\theta_1, \theta_2) 下得到最优值时

 \begin{eqnarray*} \left\{ \begin{aligned} \frac{\partial F}{\partial \theta_1} = 0\\ \frac{\partial F}{\partial \theta_2} = 0\\ \frac{\partial F}{\partial \lambda} = 0 \end{aligned} \right. \end{eqnarray*}

也就是

 \begin{eqnarray*} \left\{ \begin{aligned} \frac{\sin\theta_1}{v_1}+\lambda ~&= 0\\ \frac{\sin\theta_2}{v_2}+\lambda ~&= 0\\ \Phi(\theta_1, \theta_2) ~&= 0 \end{aligned} \right. \end{eqnarray*}

最后得到的也是

\frac{\sin\theta_1}{v_1}=\frac{\sin\theta_2}{v_2}

Miskcoo's Space,版权所有丨如未注明,均为原创
转载请注明转自:http://blog.miskcoo.com/2014/12/bzoj-3695

miskcoo

顺利从福州一中毕业!感觉大学周围都是聚聚十分可怕QAQ 想要联系的话欢迎发邮件:miskcoo [at] gmail [dot] com

One thought on “BZOJ-3695. 滑行

Leave a Reply

Your email address will not be published. Required fields are marked *

NOTE: If you want to add mathematical formulas, use $$ to wrap them. For example, use $$x_0$$ to get $$x_0$$.

If you want to get a newline, hit Enter twice, that is, use double newlines to get a newline.