2020-2021:teams:legal_string:jxm2001:动态规划_4
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:动态规划_4 [2021/04/28 22:05] jxm2001 |
2020-2021:teams:legal_string:jxm2001:动态规划_4 [2021/07/14 19:27] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 78: | 行 78: | ||
| $$ | $$ | ||
| - | f_r=\min_{l=l}^{r-1}(f_{l}+w(l,r)) | + | f_{i,j}=\min_{k=1}^{j}(f_{i-1,k}+w(k,r)) |
| + | $$ | ||
| + | |||
| + | === 性质 === | ||
| + | |||
| + | 若 $w(l,r)$ 满足四边形不等式，记 $g(i,j)$ 为最小最优决策点，则 $g(i,j)\le g(i,j+1)$。 | ||
| + | |||
| + | 考虑 $n$ 次分治法，第 $i$ 次分治法计算 $f_{i,1\sim m}$，分治过程维护最小最优决策点的上下界，时间复杂度 $O(nm\log m)$。 | ||
| + | |||
| + | <code cpp> | ||
| + | int dp[MAXN][MAXM]; | ||
| + | void solve(int pos,int nl,int nr,int ml,int mr){ | ||
| + | if(nl>nr)return; | ||
| + | int nmid=nl+nr>>1,mmid; | ||
| + | _rep(i,ml,min(mid,mr)){ | ||
| + | if(dp[pos][nmid]>dp[pos-1][i]+w(i,nmid)){ | ||
| + | dp[pos][nmid]=dp[pos-1][i]+w(i,nmid); | ||
| + | mmid=i; | ||
| + | } | ||
| + | } | ||
| + | solve(pos,nl,nmid-1,ml,mmid); | ||
| + | solve(pos,nmid+1,nr,mmid,mr); | ||
| + | } | ||
| + | </code> | ||
| + | |||
| + | === 通式 === | ||
| + | |||
| + | $$ | ||
| + | f_r=\min_{l=1}^{r-1}w(l,r) | ||
| + | $$ | ||
| + | |||
| + | 该式为类型二样例的更加一般化形式，上述解法仍然适用。 | ||
| + | |||
| + | ==== 类型三 ==== | ||
| + | |||
| + | $$ | ||
| + | f_r=\min_{l=1}^{r-1}(f_{l}+w(l,r)) | ||
| $$ | $$ | ||
| 行 85: | 行 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$ 的决策不如队列末尾的点，则无视该点。 | ||
| 行 91: | 行 127: | ||
| 否则和队列末尾的点比较在 $l_\text{tail}$ 位置的决策，如果 $i$ 更优则删去末尾的点，不断操作直到 $i$ 不再更优。 | 否则和队列末尾的点比较在 $l_\text{tail}$ 位置的决策，如果 $i$ 更优则删去末尾的点，不断操作直到 $i$ 不再更优。 | ||
| - | 最后 $i$ 和队列末尾点的最优决策分界点一定位于区间 $[l_\text{tail},r_\text{tail}]$，二分查找即可。时间复杂度 $O(n\log n)$。 | + | 最后 $i$ 和队列末尾点的最优决策分界点一定位于区间 $[l_\text{tail},r_\text{tail}]$，二分查找即可。时间复杂度 $O(n\log n)$。 |
| === 例题 === | === 例题 === | ||
| 行 161: | 行 197: | ||
| </hidden> | </hidden> | ||
| + | ==== 补充性质 ==== | ||
| + | |||
| + | - 若 $w_1,w_2$ 均满足四边形不等式(或区间包含单调性)，$c_1,c_2\ge 0$，则 $c_1w_1+c_2w_2$ 满足四边形不等式(或区间包含单调性) | ||
| + | - 若存在 $f(x),g(x)$ 使得 $w(l,r)=f(r)-g(l)$，则函数 $w(l,r)$ 满足四边形恒等式。若 $f(x),g(x)$ 单增，则 $w(l,r)$ 满足区间包含单调性。 | ||
| + | - 设 $h(x)$ 是一个凸函数，若函数 $w(l,r)$ 满足四边形恒等式并且对区间包含关系具有单调性，则复合函数 $h(w(l,r))$ 也满足四边形不等式。 | ||
2020-2021/teams/legal_string/jxm2001/动态规划_4.1619618740.txt.gz · 最后更改: 2021/04/28 22:05 由 jxm2001
