Quadrangle Optimization(四边形不等式优化) 日付: 10月 14, 2018 リンクを取得 Facebook × Pinterest メール 他のアプリ 对于DP转移方程 $$F(i, j)=min(F(i,k) + F(k+1, j))+C(i,j), \quad i \le k < j$$ $F(i,j)$表示区间的某个最优值，$C(i,j)$表示处理区间需要付出的代价。直接转移的复杂度为$O(N^3)$。定义$S(i,j)$为区间$[i,j]$的最佳决策，即使$F(i,j)$最小的$k$ 对于两个性质： 1. 包含单调性：区间的值不小于其包含的子区间的值 2. 四边形不等式：对于$a\le b < c \le d$，$V(a, c) + V(b, d) \le V(b, c) + V(a, d)$，即交叉不大于包含 对于上述转移方程和性质，有两个定理： 1. 如果$C$满足两个性质，则$F$满足四边形不等式性质 2. 如果$F$满足四边形不等式性质，则$S$单调，即$S(i,j-1)\le S(i,j) \le S(i+1, j)$ 如果$F$的四边形不等式性质成立，转移方程可以改为 $$F(i,j) = min(F(i,k) + F(k+1,j))+C(i,j), \quad S(i,j-1) \le k < min(j, S(i+1, j) + 1)$$ ## Problems [51Nod 1022. 石子归并 V2](https://kongroo.blogspot.com/2018/10/51nod-1022-v2.html) コメント
コメント
コメントを投稿