2020-2021:teams:legal_string:dp的优化
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:dp的优化 [2020/05/31 21:23] admin fix |
2020-2021:teams:legal_string:dp的优化 [2020/06/02 20:58] (当前版本) admin fix |
||
|---|---|---|---|
| 行 4: | 行 4: | ||
| - 动态转移方程 -> 状态转移方程 | - 动态转移方程 -> 状态转移方程 | ||
| - | - $(1\le j <i)$ 用前缀和就可以解决了，不需要使用单调队列。其可用于 $l_{i}\le j\le r_{i}$ 的一类 dp 转移，其中 $l_{i}$ 和 $r_{i}$ 分别单调不降 | + | - $(1\le j <i)$ 用前缀最值就可以解决了，不需要使用单调队列。其可用于 $l_{i}\le j\le r_{i}$ 的一类 dp 转移，其中 $l_{i}$ 和 $r_{i}$ 分别单调不降 |
| + | - max{} 内不仅可以是 dp[j]，还可以是任何不与 $i$ 相关的式子 | ||
| - 建议简单介绍单调队列，否则无法理解该 dp 的优化 | - 建议简单介绍单调队列，否则无法理解该 dp 的优化 | ||
| - 例题过少（提示：最经典的有单调队列优化多重背包） | - 例题过少（提示：最经典的有单调队列优化多重背包） | ||
2020-2021/teams/legal_string/dp的优化.1590931401.txt.gz · 最后更改: 2020/05/31 21:23 由 admin
