2020-2021:teams:legal_string:jxm2001:动态规划_4
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:动态规划_4 [2021/04/28 22:30] jxm2001 |
2020-2021:teams:legal_string:jxm2001:动态规划_4 [2021/07/14 19:27] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 106: | 行 106: | ||
| $$ | $$ | ||
| - | f_r=\min_{l=l}^{r-1}w(l,r) | + | f_r=\min_{l=1}^{r-1}w(l,r) |
| $$ | $$ | ||
| 行 114: | 行 114: | ||
| $$ | $$ | ||
| - | f_r=\min_{l=l}^{r-1}(f_{l}+w(l,r)) | + | f_r=\min_{l=1}^{r-1}(f_{l}+w(l,r)) |
| $$ | $$ | ||
| 行 121: | 行 121: | ||
| 若 $w(l,r)$ 满足四边形不等式，则 $f$ 具有决策单调性。记 $g(i)$ 为最小最优决策点，则 $g(i)\le g(i+1)$。 | 若 $w(l,r)$ 满足四边形不等式，则 $f$ 具有决策单调性。记 $g(i)$ 为最小最优决策点，则 $g(i)\le g(i+1)$。 | ||
| - | 考虑单调队列二分，维护每个元素的原始位置 $p$ 和负责的优决策区间 $[l,r]$。 | + | 考虑单调队列二分，维护单调队列中每个元素的决策位置 $p$ 和负责的最优决策区间 $[l,r]$。 |
| 每次新加入一个点 $i$，如果该点对序列末尾 $n$ 的决策不如队列末尾的点，则无视该点。 | 每次新加入一个点 $i$，如果该点对序列末尾 $n$ 的决策不如队列末尾的点，则无视该点。 | ||
2020-2021/teams/legal_string/jxm2001/动态规划_4.1619620248.txt.gz · 最后更改: 2021/04/28 22:30 由 jxm2001
