四边形不等式小整理

原文：四边形不等式优化dp

以下为内容摘录：

若二元函数满足当 \(a \leq b \leq c \leq d\)，有 \(w(a,d)+w(b,c) \geq w(a,c)+w(b,d)\)，则称二元函数满足四变形不等式。

二维递推优化 优化式：
\(f[l][r]=\min_{l \leq k<r}\{f[l][k]+f[k+1][r]+w[l][r]\}\)（区间递推）
\(f[i][j]=\min_{i−1 \leq k<j}\{ f[i−1][k]+w[k+1][j]\}\)（序列划分）

二维递推判定定理：对于上述优化式，如果满足

• 二元函数w满足四边形不等式
• 二元函数w满足包含单调
• 边界w(i,i)=f[i][i]=0

则f满足四边形不等式。

二维递推决策递增定理：（重要）
若上述优化式满足判定定理，设 \(p[i][j]\) 为 \(f[i][j]\) 的最优决策点,则有 \(p[l][r−1]≤p[l][r]≤p[l+1][r]\)

伪代码：

for l = 1 to n {
	for i = 1 to n-l+1 {
		j=i+l-1;
		for k = p[i][j-1] to p[i+1][j] 找到最优决策点k`并更新f[i][j]
		p[i][j]=k`;
	}
}