决策单调性

形式1(区间 dp)

\[dp_{l,r}=\min_{l \le k < r}\{dp_{l,k}+dp_{k+1,r}\}+w(l,r) \]

若 \(w(l,r)\) 满足:

  • 区间包含单调性:\(\forall l_1 \le l_2 \le r_2 \le r_1\),\(w(l_2,r_2) \le w(l_1,r_1)\)
  • 四边形不等式: \(\forall l_1 \le l_2 \le r_1 \le r_2\),\(w(l_1,r_1)+w(l_2,r_2) \le w(l_1,r_2)+w(l_2,r_1)\)

则 \(dp_{l,r}\) 满足四边形不等式,其决策点 \(op_{l,r}\) 满足:

\[op_{l,r-1} \le op_{l,r} \le op_{l+1,r} \]

复杂度降至 \(\mathcal O(n^2)\)

eg. 合并石子

形式2

\[dp_{r}=\min_{1 \le l < r}w(l,r) \]

若 \(w(l,r)\) 满足四边形不等式,则决策具有单调性。

对决策区间分治,具体来说,每次求出中点的决策点,然后分割给左右区间即可。

复杂度 \(\mathcal O(n \log n)\)

eg. Lightning Conductor

形式3

\[dp_{r}=\min_{1 \le 1 < r} \{dp_l+w(l,r)\} \]

若 \(w(l,r)\) 满足四边形不等式,则决策具有单调性。

但无法提前计算中点的决策点,不能直接分治,此时使用二分栈。

因为决策具有单调性,以任意一点为决策点的点构成一段连续的区间。

那么维护一个栈,每次用新的决策点和栈顶比较,弹出较劣的栈顶。

最后栈顶一定存在一部分区间比当前决策点有,二分找出此区间即可。

eg. 有决策单调性的题目 玩具装箱,诗人小G

形式4

\[dp_{i,j}=\min_{k < j}\{dp_{i-1,k}+w(k,j)\} \]

1.

若 \(dp_i\) 满足凸性,使用 wqs 二分得到:

\[dp_{i}=\min_{j < i}\{dp_j+w(k,j)+v\} \]

转化为形式 \(3\)

eg. 邮局加强版

2.

1.直接使用四边形不等式优化

复杂度 \(\mathcal O(n^2)\)

2.逐层计算 \(dp_i\) , 转化为形式 \(2\)

复杂度 \(\mathcal O(n^2 \log n)\)

eg. 邮局

上一篇:AIX安装单实例11gR2 GRID+DB


下一篇:hive添加自定义函数