P2571 [SCOI2010]传送带 正确性证明
查看原帖
P2571 [SCOI2010]传送带 正确性证明
230808
Zxsoul楼主2021/8/20 11:43

前言

自己YY的,感觉挺好理解的

直奔主题,证明三者中任意两者相加都能构成单峰函数

min{AMP+MNq+NMm}\min \{\frac{AM}{P}+\frac{MN}{q}+\frac{NM}{m}\}

MM 给定时, 我们来看 MNq+NMm\frac{MN}{q}+\frac{NM}{m} 存在怎么样的性质。

我们坐标表示:

M:(E,F)M:(E,F)

N:(A,B)N:(A,B)

D:(C,D)D:(C,D)

根据欧几里得距离公式我们可以写出一个优美的二元二次方程,显然从方程中看不出单峰的性质,因为它是一个园。

我们只需要保证点与点之间的距离不变,那么最小值也就不会变。这启发我们更新坐标。

我们的目的是证明出MNq+NMm\frac{MN}{q}+\frac{NM}{m}是一个单峰函数,那么我将坐标变化成理想状态,并保证点点之间距离不变,那么答案不会影响。因此我们希望将 NNDDxx 或者 yy 相同。所以旋转坐标系,如下图

image-20210820112326426

那么他们的坐标就变成:

M:(E,F)M:(E,F)

N:(A,D)N:(A,D)

D:(C,D)D:(C,D)

可以发现 N,DN,D 纵坐标 yy 相同,设 f(M)f(M) 为当 MM 点坐标 为(EF)(E,F) 时的最小值,我们将柿子列出来

f(M)=(EA)2+(FD)2q+(AC)2+(DD)2mf(M)=\frac{\sqrt{(E-A)^2+(F-D)^2}}{q}+\frac{\sqrt{(A-C)^2+(D-D)^2}}{m}

E,F,DE,F,D 是常量,那么柿子只有 AA 一个变量,那么就变成一个抛物线问题,显然是一个单峰函数。

我们再考虑 MM 是变量的时候。

同理,EFE,F 成为了变量,需要证明的是 f(M)+AMPf(M)+\frac{AM}{P} 是单峰函数。

f(M)f(M)已经知道了,只求 AMP\frac{AM}{P}就好了, 即存在 E,FE,F 两个变量,我们依旧用坐标变换,将 FF 消去,原理和上面相同。这样只剩下 EE 一个变量,又是一个单峰函数抛物线。

所以才有了三分套三分的做法。因为例外都是单峰函数

2021/8/20 11:43
加载中...