From 74e47996c5e54a38c296c881d7f0f90692ae9464 Mon Sep 17 00:00:00 2001
From: hsfzLZH1 <34390285+hsfzLZH1@users.noreply.github.com>
Date: Wed, 29 Aug 2018 21:08:49 +0800
Subject: [PATCH] Update optimization.md (#241)
MIME-Version: 1.0
Content-Type: text/plain; charset=utf8
Content-Transfer-Encoding: 8bit

* Update optimization.md

LaTeX格式又炸了。。。没有预览害死人

* Update optimization.md

* fix...
---
 docs/dp/optimization.md | 16 ++++++++--------
 1 file changed, 8 insertions(+), 8 deletions(-)

diff --git a/docs/dp/optimization.md b/docs/dp/optimization.md
index 00ae358b..9a29d6b7 100644
--- a/docs/dp/optimization.md
+++ b/docs/dp/optimization.md
@@ -10,9 +10,9 @@ By [hsfzLZH1](https://github.com/hsfzLZH1)
 
 我们首先 ** 破环成链 ** ，然后进行动态规划。设 $f_{i,j}$ 表示从位置 $i$ 合并到位置 $j$ 所能得到的最大得分， $sum_i$ 为前 $i$ 堆石子数的前缀和。
 
-写出 ** 状态转移方程 **： $f_{i,j}=max{f_{i,k}+f_{k+1,j}+(sum_j-sum_i)}(i\le k\le j)$
+写出 ** 状态转移方程 ** ： $f_{i,j}=\max\{f_{i,k}+f_{k+1,j}+(sum_j-sum_i)\}(i\le k\le j)$
 
-考虑常规的转移方法，枚举 $i$ ， $j$ 和 $k$ ，时间复杂度为 $O(n^3)$。
+考虑常规的转移方法，枚举 $i$、$j$ 和 $k$，时间复杂度为 $O(n^3)$。
 
 ### 什么是四边形不等式？
 
@@ -20,7 +20,7 @@ By [hsfzLZH1](https://github.com/hsfzLZH1)
 
 两个定理：
 
-1.四边形不等式能优化的状态转移方程能表示为 $f_{i,j}=max{f_{i,k}+f_{k+1,j}+cost(i,j)}(i\le k\le j)$。如果 $cost$ 函数同时满足单调性和四边形不等式，那么数组 $f$ 也满足四边形不等式。
+1.四边形不等式能优化的状态转移方程能表示为 $f_{i,j}=\max\{f_{i,k}+f_{k+1,j}+cost(i,j)\}(i\le k\le j)$。如果 $cost$ 函数同时满足单调性和四边形不等式，那么数组 $f$ 也满足四边形不等式。
 
 定义 $idx_{i,j}$ 为在转移 $f_{i,j}$ 的过程中在 $k=idx_{i,j}$ 时取得最小值，那么有如下定理：
 
@@ -129,21 +129,21 @@ for(int i=n;i>=1;i--)
 
 设 $f_{i,j}$ 表示在放第 $i$ 个烟花时，你的位置在 $j$ 所能获得的最大快乐值。
 
-写出 ** 状态转移方程 **：$f_{i,j}=max\{f_{i-1,k}+b_i-|a_i-j|\}$
+写出 ** 状态转移方程 ** ：$f_{i,j}=\max\{f_{i-1,k}+b_i-|a_i-j|\}$
 
 这里的 $k$ 是有范围的，$j-(t_{i+1}-t_i)\times d\le k\le j+(t_{i+1}-t_i)\times d$。
 
 我们尝试将状态转移方程进行变形：
 
-由于 $max$ 里出现了一个确定的常量 $b_i$，我们可以将它提到外面去。
+由于 $\max$ 里出现了一个确定的常量 $b_i$，我们可以将它提到外面去。
 
-$f_{i,j}=max\{f_{i-1,k}+b_i+|a_i-j|\}=max\{f_{i-1,k}+|a_i-j|\}+b_i$
+$f_{i,j}=\max\{f_{i-1,k}+b_i+|a_i-j|\}=\max\{f_{i-1,k}+|a_i-j|\}+b_i$
 
 如果确定了 $i$ 和 $j$ 的值，那么 $|a_i-j|$ 的值也是确定的，也可以将这一部分提到外面去。
 
-最后，式子变成了这个样子：$f_{i,j}=max\{f_{i-1,k}+|a_i-j|\}+b_i=max\{f_{i-1,k}\}+|a_i-j|+b_i$
+最后，式子变成了这个样子：$f_{i,j}=\max\{f_{i-1,k}+|a_i-j|\}+b_i=\max\{f_{i-1,k}\}+|a_i-j|+b_i$
 
-看到这一熟悉的形式，我们想到了什么？** 单调队列优化 **。由于最终式子中的 $max$ 只和上一状态中连续的一段的最大值有关，所以我们在计算一个新的 $i$ 的状态值时候只需将原来的 $f_{i-1}$ 构造成一个单调队列，并维护单调队列，使得其能在均摊 $O(1)$ 的时间复杂度内计算出 $max\{f_{i-1,k}\}$ 的值，从而根据公式计算出 $f_{i,j}$ 的值。
+看到这一熟悉的形式，我们想到了什么？** 单调队列优化 **。由于最终式子中的 $\max$ 只和上一状态中连续的一段的最大值有关，所以我们在计算一个新的 $i$ 的状态值时候只需将原来的 $f_{i-1}$ 构造成一个单调队列，并维护单调队列，使得其能在均摊 $O(1)$ 的时间复杂度内计算出 $\max\{f_{i-1,k}\}$ 的值，从而根据公式计算出 $f_{i,j}$ 的值。
 
 总的时间复杂度为 $O(n\times m)$。
 
-- 
2.11.0