2020-2021:teams:legal_string:dp的优化
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:dp的优化 [2020/05/31 19:35] admin update |
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的优化 ====== | ||
| 行 15: | 行 25: | ||
| \begin{cases} | \begin{cases} | ||
| &\text{sum}[i]&i\le k\\ | &\text{sum}[i]&i\le k\\ | ||
| - | &\max\{dp[j-1]+\sum[i]-\sum[j]\}&i-k \le j\le i,i>k | + | &\max\{dp[j-1]+\text{sum}[i]-\text{sum}[j]\}&i-k \le j\le i,i>k |
| \end{cases} | \end{cases} | ||
| $$ | $$ | ||
| 行 24: | 行 34: | ||
| 注意到 $\text{sum}[i]$ 可以直接提出，即 $dp[i]=\max\{dp[j]\}+\text{sum}[i]$，所以我们只需用一个单调队列来维护 $dp[i]$ 的最值，复杂度可以降低为 $O(n)$。 | 注意到 $\text{sum}[i]$ 可以直接提出，即 $dp[i]=\max\{dp[j]\}+\text{sum}[i]$，所以我们只需用一个单调队列来维护 $dp[i]$ 的最值，复杂度可以降低为 $O(n)$。 | ||
| - | |||
| - | 代码 | ||
| <hidden 代码> | <hidden 代码> | ||
2020-2021/teams/legal_string/dp的优化.1590924916.txt.gz · 最后更改: 2020/05/31 19:35 由 admin
