总结了一些动态规划问题的优化方法。
四边形不等式:
称代价函数 w 满足凸四边形不等式,当:\(w(a,c)+w(b,d)\le w(b,c)+w(a,d),\ a < b < c < d\) 如下所示,区间1、2对应的 w 之和 ≤ 3、4之和
\[ \underbrace {\overbrace {a \to \underbrace{b \to c}_3}^1 \to d }_4 \llap{\overbrace {\phantom{b\to c\to d}}^2}\]
凸完全单调性:
称矩阵 \(A\) 凸完全单调,当: \(A(a,c)\ge A(b,c)\Rightarrow A(a,d)\ge A(b,d),\ a < b < c < d\) 如下所示,如果满足1区间对应的 w 比2大,那么可以推出3比4大。
\[ \overbrace {\overbrace {a \to b \to c}^1 \to d }^3 \llap{\underbrace {\underbrace{\phantom{b\to c}}_2\phantom{\to d}}_4}\]
由四边形不等式可以推出完全单调性,反之不真。
转移方程:\(f(j)=\min_{i < j}\{f(i)+w(i,j)\}\)
令 \(A(i,j)=f(i)+w(i,j)\)表示状态 j 从上一列的第 i 行转移过来的结果。
w满足凸四边形不等式\(\Rightarrow\)w 是凸完全单调的\(\Rightarrow A\)也是凸完全单调的\(\Rightarrow\)决策单调。
令 d(j) 表示最小的满足第 j 行比前面行优的列编号。
每个决策(行)的作用范围是相互连接且递增的列区间,d(j)就是j作用区间的起点,比如:
111224444,d(1)=1,d(2)=4,d(4)=6
由于决策单调,我们用栈维护\(< d(j),j>\)。每次要做的就是:
这样就从\(O(n^2)\)优化到了\(O(n\log_2n)\)。
转移方程:\(f(i,j)=\min \{f(i-1,k-1)+w(k,j)\}\)
也是利用决策单调性。
令 d(i, j) 表示 f(i, j) 的最优决策。
\(d(i,j')\le d(i,j) ,j' < j\)
于是可以在d(i, j) 前面的区间遍历寻找d(i', j')。
我们分治的过程 \(solve(opt_L,opt_R,l,r)\) 遍历\(opt_L\)到\(opt_R\) 计算出中点\(m=(l+r)/2\) 的 d(i, m)。
那么所有\(l\le x < m\) 的 d(i, x) 一定是在\([opt_L, d(i,m)]\)区间内,所有\(m < x\le r\)的d(i, x) 一定是在\([d(i,m),opt_R]\)区间内。 所以递归:
solve(optL,d[i][m],l,m-1);
solve(d[i][m],optR,m+1,r);
相关文章:post1
转移方程:\(\displaystyle f(i)=\min_{j=b[i]}^{i-1}\{g(j)\} + w(i)\),\(b[i]\)随 i 递增。 若后面的一个决策更优,那么前面的决策就可以删掉。因此单调队列维护决策表:
转移方程: \(f(i)=\min\{a_{i}\cdot x_{j} + b_{i} \cdot y_{j}\}\)
这是一种数形结合的思想。将每个决策作为一个点\((x_j,y_j)\),画在平面直角坐标系中,于是我们要找的是让\(z=a_{i}\cdot x+ b_{i} \cdot y\) 最小的点。变形得到\(y=-\frac {a_i}{b_i} \cdot x+\frac z {b_i}\)。也就是找一个点,斜率为\(-\frac {a_i} {b_i}\)的直线经过该点时,纵截距最小。
可以发现所有最优决策点在一个凸壳上。
相关文章: bzoj1492 [NOI2007]货币兑换Cash
转移方程:\(f(i)=\min \{f(j)+b_j*a_i\}\)
其实相当于上式\(a_i=1,x_j=f(j),y_j=b_j,b_i=a_i\),因此也可以用斜率优化。
将每个决策\(A(i,j)=\color{blue}{b_j}*a_i+\color{green}{f(j)}\)
作为一条直线\(y=\color{blue} {m_j}*x+\color{green}{c_j}\),当前状态选择的决策就是将\(x=a_i\)带入所有直线,得到最小值的那条直线。
我们用栈维护有效(最小值可能出现在它上面)的直线。
如果\(b_j\)递减,那么相当于不断加入一条斜率更小的直线,它和最后一条直线\(l_1\)的交点如果比\(l_1\)与\(l_2\)的横坐标要更小,则\(l_1\)无效了,从栈中弹出,反复执行直到横坐标不更小或者只剩栈底,此时入栈。这个过程类似维护凸包。
如果\(a_i\)递增,那么每次最小值一定在最后一条直线上。于是复杂度是\(O(n)\)。
相关文章:Convex hull trick
转移方程:\(f(i,j)=\min \{f(i-1,k)+b_k*a_j\}\)
i 固定时,每个决策\(A(j,k)=\color{blue}{b_k}*a_j+\color{green}{f(i-1,k)}\),作为一条直线\(y=\color{blue} {m_k}*x+\color{green}{c_k}\),那么接下来同上。 故总得复杂度是\(O(kn)\)。
相关文章: post2
转移方程 \(f(i,j)=\min\{f(i,k-1)+f(k,j)\}+w(i,j)\)
于是转移方程改写为:
\(f(i,j)=\min\{ f(i,k-1)+f(k,j)\}+w(i,j), s(i,j-1)\le k\le s(i+1,j)\)
由于这个状态转移方程枚举的是区间长度L,假设求f(i,i+L),而每次循环长度之和为
\[ \begin{aligned} &\sum_{i=1}^{n-L}{s(i+1,i+L)-s(i,i+L-1)}\\ &=s(2,L+1)-s(1,L)+s(3,L+2)-s(2,L+1)+s(4,L+3)-s(3,L+2)..\\ &=s(n-L+1,n)-s(1,L)\le n-1 \end{aligned}\]
枚举L是的\(O(n)\),于是总的复杂度是\(O(n^2)\)。
Donald E. Knuth 从最优二叉搜索树的数据结构中提出的。
参考文章:
(来自之前的博客,不记得内容最后更新时间了 )