2020-2021:teams:legal_string:dp的优化
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:dp的优化 [2020/05/31 16:44] admin ↷ 页面2020-2021:teams:legal_string:dp的优化被移动并更名为2020-2021: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的优化 ====== | ||
| ===== 一、单调队列优化 ===== | ===== 一、单调队列优化 ===== | ||
| - | 单调队列优化，可以降低诸如$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]] | [[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> | <code cpp> | ||
| #include <stdio.h> | #include <stdio.h> | ||
| 行 58: | 行 75: | ||
| } | } | ||
| </code> | </code> | ||
| + | </hidden> | ||
| ==== 练习 ==== | ==== 练习 ==== | ||
2020-2021/teams/legal_string/dp的优化.1590914667.txt.gz · 最后更改: 2020/05/31 16:44 由 admin
