コミット: master - OI-wiki (git)

:star2: Wiki of OI / ICPC for everyone. （某大型游戏线上攻略，内含炫酷算术魔法）

コミットメタ情報

• リビジョン: 16b5541317d0daf6c329385878d7dd1667011d10 (tree)
• 日時: 2021-01-30 20:10:29
• 作者: Shuhao Zhang <studyingfather@gmai...>
• コミッター: GitHub

ログメッセージ

Merge pull request #2943 from Luckyblock233/patch-5

fix(slope): fix typo

変更サマリ

• modified: docs/dp/opt/slope.md

差分

--- a/docs/dp/opt/slope.md
+++ b/docs/dp/opt/slope.md
@@ -38,7 +38,7 @@ $$
 
 如图，我们将这个斜率为 $k_i$ 的直线从下往上平移，直到有一个点 $(x_p,y_p)$ 在这条直线上，则有 $b_i=y_p-k_ix_p$ ，这时 $b_i$ 取到最小值。算完 $f_i$ ，我们就把 $(x_i,y_i)$ 这个点加入点集中，以做为新的 DP 决策。那么，我们该如何维护点集？
 
-容易发现，可能让 $b_i$ 取到最小值的点一定在下凸壳上。因此在寻找 $p$ 的时候我们不需要枚举所有 $i-1$ 个点，只需要考虑凸包上的点。而在本题中 $k_i$ 随 $i$ 的增加而递减，因此我们可以单调队列维护凸包。
+容易发现，可能让 $b_i$ 取到最小值的点一定在下凸壳上。因此在寻找 $p$ 的时候我们不需要枚举所有 $i-1$ 个点，只需要考虑凸包上的点。而在本题中 $k_i$ 随 $i$ 的增加而递增，因此我们可以单调队列维护凸包。
 
 具体地，设 $K(a,b)$ 表示过 $(x_a,y_a)$ 和 $(x_b,y_b)$ 的直线的斜率。考虑队列 $q_l,q_{l+1},\ldots,q_r$ ，维护的是下凸壳上的点。也就是说，对于 $l<i<r$ ，始终有 $K(q_{i-1},q_i) < K(q_i,q_{i+1})$ 成立。