2020-2021:teams:legal_string:dp的优化

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:legal_string:dp的优化 [2020/05/31 16:45]
admin ↷ 页面2020-2021:technique:dp_optimization被移动至technique:dp_optimization
+++ 2020-2021:teams:legal_string:dp的优化 [2020/06/02 20:58] (当前版本)
admin fix
@@ 行 1: / 行 1: @@
+**格式**：max 使用 \max，sum 使用 \text{sum}，代码使用 ''<hidden></hidden>'' 隐藏，均已修改。学会使用 ''\begin{cases}\end{cases}'' 来表示不同的 case，不需要自己设计格式。
+**内容**：内容过于简单！可尝试从读者的角度想想能否看懂。
+  - 动态转移方程 -> 状态转移方程
+  - $(1\le j <i)$ 用前缀最值就可以解决了，不需要使用单调队列。其可用于 $l_{i}\le j\le r_{i}$ 的一类 dp 转移，其中 $l_{i}$ 和 $r_{i}$ 分别单调不降
+  - max{} 内不仅可以是 dp[j]，还可以是任何不与 $i$ 相关的式子
+  - 建议简单介绍单调队列，否则无法理解该 dp 的优化
+  - 例题过少（提示：最经典的有单调队列优化多重背包）
 ====== dp的优化 ======
 ===== 一、单调队列优化 =====
-单调队列优化，可以降低诸如$dp[i]=max\{dp[j]\}+C[i](1\le j <i)$这样的动态转移方程的时间复杂度。主要的原理就是利用一个单调队列来维护$dp[i]$的最值。
+单调队列优化，可以降低诸如 $dp[i]=\max\{dp[j]\}+C[i](1\le j <i)$ 这样的状态转移方程的时间复杂度。主要原理是利用一个单调队列来维护 $dp[i]$ 的最值。
 ==== 一道例题 ====
@@ 行 9: / 行 19: @@
 [[https://www.luogu.com.cn/problem/P2627|洛谷p2627]]
-我们不难写出动态转移方程$dp[i]=\left\{\begin{aligned} sum[i],i\le k\\max\{dp[j-1]+sum[i]-sum[j]\}(i-k \le j\le i,i>k)\end{aligned}\right.$
+我们不难写出状态转移方程
-答案为$ans=max\{dp[i]\}$
+$$
+dp[i]=
+\begin{cases}
+&\text{sum}[i]&i\le k\\
+&\max\{dp[j-1]+\text{sum}[i]-\text{sum}[j]\}&i-k \le j\le i,i>k
+\end{cases}
+$$
-但是时间复杂度为$O(nk)$，显然会超时
+答案为 $\text{ans}=\max\{dp[i]\}$。
-注意到$sum[i]$可以直接提出，即$dp[i]=max\{dp[j]\}+sum[i]$，所以我们只需用一个单调队列来维护$dp[i]$的最值，复杂度可以降低为$O(n)$
+但是时间复杂度为 $O(nk)$，显然会超时。
-代码
+注意到 $\text{sum}[i]$ 可以直接提出，即 $dp[i]=\max\{dp[j]\}+\text{sum}[i]$，所以我们只需用一个单调队列来维护 $dp[i]$ 的最值，复杂度可以降低为 $O(n)$。
+<hidden 代码>
 <code cpp>
 #include <stdio.h>
@@ 行 58: / 行 75: @@
 }
 </code>
+</hidden>
 ==== 练习 ====

2020-2021/teams/legal_string/dp的优化.1590914722.txt.gz · 最后更改: 2020/05/31 16:45 由 admin